Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability
Authors: Alec Farid
Anirudha Majumdar
Venue: NeurIPS 2021 Poster (2021)
Keywords: Meta Learning
Statistical Learning Theory

Abstract: We are motivated by the problem of providing strong generalization guarantees in the context of meta-learning. Existing generalization bounds are either challenging to evaluate or provide vacuous guarantees in even relatively simple settings. We derive a probably approximately correct (PAC) bound for gradient-based meta-learning using two different generalization frameworks in order to deal with the qualitatively different challenges of generalization at the "base" and "meta" levels. We employ bounds for uniformly stable algorithms at the base level and bounds from the PAC-Bayes framework at the meta level. The result of this approach is a novel PAC bound that is tighter when the base learner adapts quickly, which is precisely the goal of meta-learning. We show that our bound provides a tighter guarantee than other bounds on a toy non-convex problem on the unit sphere and a text-based classification example. We also present a practical regularization scheme motivated by the bound in settings where the bound is loose and demonstrate improved performance over baseline techniques.

Generalization Bounds for Meta-Learning via PAC- PAC-Bayes and Uniform Stability
Alec Farid Department of Mechanical and Aerospace Engineering, Princeton University (afarid, ani .ww.umdarrraa.a.mmmmmm (eajjudda//prrinceee Sprincettnninnnnnee
Anirudha Majumdar
Abstract
We are motivated by the problem of providing strong generalization guarantees the context of meta-learning. Existing generalization bounds either challenging to evaluate or provide vacuous guarantees in even relatively simple settings. We derive probably approximately correct (PAC) bound for gradient-based meta- learning using two different generalization frameworks order to deal with the qualitatively different challenges of generalization at the "base" and "meta" levels. We employ bounds for uniformly stable algorithms at the base level and bounds from the PAC-Bayes framework the meta level. The result of this approach is novel PAC bound that is tighter when the base learner adapts quickly, which is precisely the goal of meta-learning. We show that our bound provides tighter guarantee than other bounds on toy non-convex problem on the unit sphere and a text-based classification example. We also present a practical regularization scheme motivated by the bound in settings where the bound is loose and demonstrate improved performance over baseline techniques.
Introduction
A major challenge with current machine learning systems is the need to acquire large amounts of training data in order to learn a new task. Over the past few decades, meta-learning [2] 70 has emerged as promising avenue for addressing this challenge. Meta-learning relies on the intuition that a new task often bears significant similarity to previous tasks; hence, learner can learn to perform
task very quickly by exploiting data from previously-encoune encountered related tasks. The meta-learning problem formulation thus assumes access to datasets from a variety of tasks during meta-training. The goal of the meta learner is then to learn inductive biases from these tasks in order to train a base learner to achieve few-shot generalization on new task.
Over the past few years, there has been tremendous progress in practical algorithms for meta- learning (see, e.g., [6 255 (2)). Techniques such as model-agnostic meta-learning (MAML) 25 have demonstrated the ability to perform few-shot learning in variety of supervised learning and reinforcement learning domains. However, our theoretical understanding these techniques lags significantly behind successes on the empirical front. In particular, the problem of deriving generalization bounds for meta-leamnn weta-lca techniques remains an outstanding challenge. Current methods for obtaining generalization guarantees for meta-learning [5] 34 77) either (i) produce bounds that are extremely challenging to compute or (ii) produce vacuous or near-vacuous bounds in even highly simplified settings (see Section 5 for numerical examples). Indeed, we note that existing work on generalization theory for meta-learning techniques do not explicitly report numerical values for generalization bounds. This is in contrast to the state of generalization theory in the supervised learning setting, where recent techniques demonstrate the ability to obtain non-vacus vacuous generalization guarantees benchmark problems (e.g. visual classification problems 24 78
The generalization challenge in meta-learning similar to, but distinct from, the supervised learning case. In particular, any generalization bound for meta-learning must account for two levels of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

generalization. First, one must account for generalization at the base level, i.e., the ability of the base learner to perform well on new data from a given task. This is particularly important in the few-shot learning setting. Second, one must account for generalization at the meta level, i.e., the ability of the meta learner to generalize to new tasks not encountered during meta-training. Moreover, the generalization performance at the two levels is coupled since the meta learner is responsible for learning inductive biases that the base learner can exploit for future tasks.
The key technical insight of this work is to bound the generalization error at the two levels (base and meta) using two different generalization theory frameworks that each are particularly well-suited for addressing the specific challenges of generalization. At the base level, we utilize the fact that a learning algorithm that exhibits uniform stability [4 [5] also generalizes well in expectation (see Section 4.1 for a formal statement). Intuitively, uniform stability quantifies the sensitivity of the output of a learning algorithm to changes in the training dataset. As demonstrated by 29 limiting the number of training epochs of gradient-basel learning algorithm leads to uniform stability. In other words, a gradient-based algorithm that learns quickly is stable. Since the goal of meta-learning is precisely to train the base learner to learn quickly, posit that generalization bounds based on stability are particularly well-suited to bounding the generalization error at the base level. At the meta level, we employ generalization bound based on Probably Approximately Correct ( (PAC)-Bayer theory. Originally developed two decades ago 4 BSJ, there has been a recent resurgence of interest in PAC- Bayes due to its ability to provide strong generalization guarantees for neural networks 24 8 15.. Intuitively. the challenge of generalization at the meta level (i.e., generalizing to new tasks) is similar to the challenge of generalizing to new data in the standard supervised learning setting. In both cases, one must prevent over-fitting to the particular tasks/data that have been seen during meta-training/raiiing. Thus, the strong empirical performance of PAC-Bayes theory in supervised learning problems makes it a promising candidate for bounding the generalization error at the meta level.
Contributions. The primary contributions of this work are the following. First, we leverage the insights above in order to develop a novel generalization bound for gradient-based meta-learning using uniform stability and PAC-Bayes theory (Theorem 3). Second, we develop a regularization scheme for MAML 225 that explicitly minimizes the derived bound (Algorithm D.. We refer to the resulting approach as PAC-BUS since it combines PAC- PAC-Bayes and Uniform Stability to derive generalization guarantees for meta-learning. Third, we demonstrate our approach on two meta- learning problems: (i) a toy non-convex classification problem on the unit-ball (Section J. and (ii) the Mini-Wikk benchmark introduced in 62! (Section 5.2 Even in these relatively small-scale settings, we demonstrate that recently-develppe generalization frameworks for meta-learning provide either near-vacuous or loose bounds, while PAC-BUS provides significantly stronger bounds. Fourth, we demonstrate our approach in larger-scale settings where it remains challenging to obtain non- vacuous bounds (for our approach as well as others). Here, we propose a practical regularization scheme which re-weights the terms in the agorously-deriver PAC-BUS upper bound (PAC-BUS(H); Algorithm in the appendix). Recent work (77 introduces a challenging variant of the Omniglot benchmark 35 which highlights and tackles challenges with memorization in meta-learning, We show that PAC-BUS(H) is able to prevent memorization on this variant (Section 5.3).
2 Problem formulation
Samples, tasks, and datasets. Formally, consider the setting where we have an unknown meta distribution P; over tasks (roughly, "tasks" correspond to different, but potentially related, learning problems). A sampled task ~ Pt induces an (unknown) distribution Ps. a over sample space Z. We assume that all sampling is independent and identically distributed (i.i.d).. Note that the sample space Z is shared between tasks, but the distribution Ps+ may be different. We then sample within-task samples ~ Paje and within-task datasets S = [21, (2,,,2,,... 22, =m} ~ pm. We assume that each sample z has a single corresponding label o(2), where the function o is an oracle which outputs the correct label of 2. At meta- peatiiraining time, we assume access to / datasets, which we call S (St. Sg. ..... Si). Each dataset S, in S is drawn by first selecting a task t, from P,, and then drawing S. ~ Plf.
Hypotheses and losses. Let h denote hypothesis and L(h, z) be the loss incurred by hypothesis h on sample z. The loss is computed by comparing h())) with the true label o(z). For simplicity, we assume that there is no noise on the labels; we can thus assume that all loss functions have access to

---

the label oracle function and thus the loss depends only on hypothesis h and sample 2. We note that this assumption not required for our analysis and is made for the ease of exposition. Overloading the notation, we let Lh,, Pate) == Pa Lh,, z) and (h,, S) =- T Σ |s| Lhh, zi).
Meta-laarning. As with model-agnostic meta-learning (MAMI.)
25 we let meta parameters 0 E Th correspond to initialization of the base learner's hypothesis. Let hi be the 0-initialized hypothesis. Generally, the initialization 0 is learned from the multiple datasets we have access to at meta-training time. In this work, we will learn a distribution Po over initializations so that we can use bounds from the PAC-Bayes framework. At test time, a new task & ~ P: is sampled and we are provided with a new dataset S P The base learner uses an algorithm A (e.g., gradient descent), the dataset S, and the initialization 0 ~ Pg in order to fine-tune the hypothesis and perform well on future samples drawn from P-jt.. We denote the base learner's 's updated hypothesis by hA(0,5). More formally, our goal is to learn a distribution Pe with the following objective:
min C(Po, = min E Po P.
E
E P~Po
L(hA(0.S): Paje).
(1)
S-P.. s/c
We are particularly interested in the the few-shot learning case, where the number of samples which the base learner can use to adapt is small. A common technique to improve test performance in the few-shot learning case is to allow for validation data at meta-training time. Thus, in addition to generalization guarantee on meta-learning without validation data, we will derive a bound when allowing for the use of validation data S.a ~ 2je during meta-training.
3 Related work
Meta-learning. Meta-learning is a well-studied technique for exploiting similarities between learning tasks [62 701- Often used to reduce the need for large amounts of training data, number of
approaches for meta-learning have been explored over decades []] [3
16
31
/2
61
55 (2)
Recently, methods based on model-agnostic meta-learning (MAML) 25 have demonstrated strong performance across different application domains and benchmarks such as Ommiglol (55 and Mini- ImageNet (74). These methods operate by optimizing set of initial parameters that can be quickly fine-tuned via gradient descent on a new task. The approaches mentioned above typically do not provide any generalization guarantees, and none of them compute explicit numerical bounds on generalization performance. Our approach has the structure of gradient-base based meta-learning while providing guarantees on generalization.
Generalization bounds for supervised learning. Multiple frameworks have been developed for providing generalization guarantees in the classical supervised learning setting. Early breakthroughs include Aopnik-Chervonenke (VC) theory [71
6
Rademacher complexity (65. and the minimum
description length principle 112 56
36) More recent frameworks include algorithmic stability
bounds [1 19 29 57 and PAC-Bayes theory 67
The connection between stability and learnability has been established in [66 73 29), and suggests that algorithmic stability bounds are a strong choice of generalization framework. PAC-Bayes theory in particular provides some of the tightest known gencralization bounds for classical supervised learning approaches such as support 4. 4 Since its development, researchers have continued to tighten
34
vector machines (44 38 27
57
38 and generalize the framework 17
18 59 Exciting recent results 24 45 10
54
have demonstrated the promise of PAC-Bayes to provide strong generalization bounds for neural for recent review of generalization bounds for neural networks). It is also possible to combine frameworks such as PAC-Bayes and uniform stability to derive bounds for supervised learning 33 We will use these two frameworks to bound generalization in the two levels of meta-learning. In contrast to the standard supervised learning setting, generalization bounds for meta-lcarning are less common and remain loose.
networks on supervised learning problems (see (63)
Generalization bounds for meta-learning, As described in Section I meta-learning bounds must account for two "levels" of generalization (base level and meta level). The approach presented in 41 utilizes algorithmic stability bounds at both levels. However, this requires both meta and base learners to be uniformly stable. This is strong requirement that challenging to ensure at the meta level. Another recent method, known as follow-the walloo-the-meta-reguueee wet---metearrrraee regetaargguarrzze-leeeddee (FMRL) [4], provides guarantees for a regularized meta-learning version of the followethe-leader (FTL) method for online learning, see e.g. 300 The generalization bounds provided are derived from the application of
online-to-batee techniques K 222. A regret bound for meta-learning using an aggregation technique at the meta-level and algorithm with uniform generalization bound at the base level is provided
3

---

in 31. The techniques mentioned do not present an algorithm which makes use of validation data (in contrast to our approach). Using validation data (i.e., held-out data) common technique for improving performance in meta-learning and is particularly important for the few-shot learning case.
Another method for deriving generalization bound meta-leamiig is to PAC-Bayes bounds at both the base and meta levels [52] 533. In [51, generalization bounds based on such a framework are provided along with practical optimization techniques. However, the method requires one to maintain distributions over distributions of initializations, which can result in large computation times during training and makes extremely challenging to numerically compute the bound. Moreover, the approach also does not allow one to incorporate validation data to improve the bound. Recent work has made progress on some of these challenges. In (60), the computational efficiency of training is improved but the challenges associated with numerically computing the generalization bound or incorporating validation data are not addressed. State-of-the- PAC-Bayes guarantee, addresses computation times for training and evaluation of the bound, and allows for validation data 77 However, all of the two-level PAC-Bayes bounds require a separate PAC-Bayes bound for each task, and thus potentially loose union bound.
work tightens the two-level
We present framework which, to our knowledge, is the first to combine algorithmic stability and PAC-Bayes bounds (at the base- and meta- levels respectively) in order to derive meta-learning algorithm with associated generalization guarantees. As outlined in Section I we believe that the algorithmic stability and PAC-Bayes frameworks are particularly well-suited to tackling the specific challenges of generalization the different levels. We also highlight that none of the approaches mentioned above report numerical values for generalization bounds, even for relatively simple problems. Here, we empirically demonstrate that prior approaches tend to provide either near-vacuous or loose bounds even in relatively small-scale settings while our proposed method provides significantly stronger bounds.
4 Generalization bound on meta-learning
We use two different frameworks for the two levels of generalization required in meta-learning bound. We utilize the PAC-Bayes framework to bound the expected training loss on future tasks, and uniform stability bounds to argue that if we have a low training loss when using uniformly stable algorithm, then we achieve a low test loss. The following section will introduce these frameworks independently. We then present the overall meta-learning bound and associated algorithm to find distribution over initialization parameters (i.e., meta parameters) that minimizes the upper bound.
4.1 Preliminaries: two generalization frameworks
4.1.1 Uniform stability
Let S = =[2,, 22..,, 2m3 E t be a set of m elements of Z. Let S = ( Zi- 2/, 1i4 } } be identical to dataset S except that the 7th sample z; is replaced by some z/ E Z. Note that our analysis can be extended to allow for losses bounded by some finite M, but work with losses bounded within [0. 1] for the sake of simplicity. With these precursors, we define an analogous notion of uniform stability to [29] Definition 2.1] for deterministic algorithms A and distributions Pe over initializations! |
Definition (Uniform Stability) A determiiistc algorithm A has B > O uniform stability with respect (1....,m}, and all distributions Pg over initializations, the to loss L if V E Z, V 2mh Vi following holds:
[[(hA(,,))) 2) - [(hA(o.s)) 8~Po
E
(2)
We define Bus as the minimal such B.
In this work, we will bound Bus as a function of the algorithm, form of the loss, and number of samples that the algorithm uses (See Appendix A.4 for further details on the bounds on Bus for our setup). We then establish a relationship between uniform stability and generalization in expectation. The following is adapted from 2 Theorem 2.2] for the notion of uniform stability presented in Definition II
We use deterministic algorithms to avoid excess computation when calculating the provided meta-learning upper bounds. See Appendix A.4 for further details.

---

Theorem (Algorithmic Stability Generalization in Expectation) Fix task t ~ Pt. The following inequality holds for hypothesis h A(0,S) learned using Bus uniformly stable algoritim A with respect to loss L;
E Pr S 2lt
A( Pet) Supm ale
E
E BrrP
[hhA( + Bus-
Proof.
The proof similar to the one presented for 29 Theorem 2.2] and is presented in Appendix
A1
4.1.2 PAC-Bayes theory
For the meta-level bound, we make use of the PAC-Bayes generalization bound introduced in 45 Note that other PAC-Bayes bounds such as the quadratic variant [58] and PAC- MAC-Bayes-A variant 69
may be used and substituted in the following analysis. We first present general version of the PAC-Bayes bound and then specialize it to our meta-learning setting in Section 4.2 Let [(0, 8) be arbitrary loss function which only depends on parameters 0 and the sample & which has been drawn from an arbitrary distribution P.- The following bound is tightened version of the bound presented in 4
for when 2 8.
For any data-independent prior distribution Po.o over 0, some loss function f where 0 S f(0,s) I 1, V.V. s, 6, 1 122 8, and 8 E (0, with probability at least 1- ô over sampling of {s1, .......... 81} Pt, the following holds simultaneously for all distributions Po over 0:
Theorem 2 (PAC-Bayes Generalization Bound 40
f(0,8)
Σ
E 0~1
f(0,8:) + PP
(4)
8rrP, O
where the PAC-Bayes "regularizer" term defined as follows
DKL. (Pol + In 2y
RPAC-B(Po, Pooc.B.P 8,1)
(5)
21
and DKL is the Kullback-Leible (KL) divergence.
4.2 Meta-learning bound
In order to obtain a generalization guarantee for meta-learning, we utilize the two frameworks above. We first specialize the PAC-Bayes bound Theorem 2 bound the expected training loss on future tasks. We then utilize Theorem to demonstrate that if we have a low expected training loss when using a uniformly stable algorithm, then we achieve low expected test loss. These two steps allow us to combine the generalization frameworks above to derive an upper bound on (I which can be computed with known quantities. With the following assumption, the resulting generalization bound is presented in Theorem B
Assumption (Bounded loss.) The loss function L is bounded: 0 S L(h, 2) S 1 for any h in the hypothesis space for the given problem, and any z in the sample space.
Theorem (Meta-l Generalization Guarantee) For hypotheses Ate.s) learned with Bus uniformly stable algorithm A, data-independent prior Po.o over initializations 0, loss L. which satisfies Assumption 2 8, and 8 E (0, 1), with probability at least 1 - over a sampling of the meta-trod eeta-traaiiin dataset S ~ Psz, the following holds simultaneously for all distributions Po over A:
C(Po, P.) E +
Σ
E. ((hao.s)), S.) + RPAC-n Pa.o. 8,1) Bus.
(6)
B~Po
Proof. The proof can be split into three steps:
Step 1.
Let P. in Theorem 2 be the marginal distribution Ps over datasets of size m (see Appendix A.2 for details) and note that sampling S ~ Ps is equivalent to first sampling ~ Pt and then sampling
S pmm Additionally let S) = L(h S) where A(0, S) is any deterministic algorithm.
5

---

Plugging in these definitions into Inequality results in the following inequality which holds under the same assumptions as Theorem 2
and with probability at least - ò over the sampling of Ps:
E I [(hA(o.s): SmPs 0~1%
E [(hAco,s),
trPe SpP 0-Pb
E [(ha(o,s.) Si) + RPAc-B(Po. Po.,,,,
Po
Step
Now assume that algorithm A is Bus uniformly stable. For fixed task Pe we have the following by Theorem
E Or-Po
A(hAce,)) pat)
E
E [(hA(O.5):
Bus-
SrPP alt
SruPi anPo
Take the expectation over t ~ P.. We then have:
E t-
E L(haco.s), P2t) t-
E
E 0-1%
[(hA(o,s):S) Bus,
(8)
Smpm Dr olt
S-Pm 2it
since E,-P, Bus Bus. This establishes bound on the true expected loss for a new task after running algorithm A on training dataset corresponding to the new task. Step
provides an upper bound on the first term of the RHS of (8) when algorithm A is Bus Note that 77)
uniformly stable. Thus we have the following by plugging 7 in the RHS of (8):
Under the same assumptions as both Theorems [ndd] 2 and with probability at least 1 - over the sampling S P'':
E E
E (lhr(o,s),Pa S S.P. a~Ps
Σ
E [(hAio,s), + RPxc- Po.o, + Bus, P~Po
completing the proof.
Theorem 3 is presented for any distributions Po and Po.o over initializations. However, in practice we will use multivariate Gaussian distributions for both. The specialization of Theorem to Gaussian distributions is provided in Appendix A...I Next, meta-training time so that the bound is more suited to the few-shot learning case. We compute the upper bound using the evaluation data S.. = {S, S.n. sampled from the marginal distribution Ps.. still only require m samples at meta-test time; Appendix A.3.2 for the derivation. Note that the training data is often excluded from the data used to update the meta-learner. However, this is necessary for our approach to obtain a guarantee on few-shot learning performance. The result is guarantee with high probability over sampling of Sev Ps..:
allow for validation data Sva PPt at
over datasets of size mn However,
C(Po, Pt) S 7
Σ
E [(hA(o.s.), Sev.)) + RPAC- Poo,, PNPy
mêus
m +
4.3 PAC-BUS algorithm
Recall that aim to find a distribution Py over initializations that minimizes L(Pg, Pt) stated in Equation ( We cannot minimize [(Pp. Pt) directly due to the expectations taken over unknown distributions P. and Ps for sampled task t, but may indirectly minimize by minimizing the upper bounds in Inequalities
or
Computing the upper bound requires evaluating an expectation taken over ~ Po. In general, this intractable. However, we aim to minimize this upper bound provide the tightest guarantee possible. Similar to the method in [24], we use unbiased estimator of Eş- L(h Let Pe be a multivariate Gaussian distribution over initializations f with mean and covariance diag(s); (s); thus Po (u,, ds)g and Po. N(Hn, diag(so)). Further, let & == log(s,, and use the shorthand Nis for the prior and N3 for the posterior distribution over initializations. We use the following estimator of Eg A(
L(hA(0,S):))) ) 0 8~ Ng.
(10)

---

Algorithm PAC-BUS: meta-learning via PAC-Bayes and Uniform Stability
Input: Fixed prior distribution Nyin over initializations
Input: Sus uniformly stable Algorithm A
Input:
Meta-training training dataset S, learning rate "y
Initialize: 2) + 4/0
Output: Optimized 2h*
B 88, 0..00........ 0 := Ei= I(ho, Si) + REAC (NG, 6,1) Bus
while not converged do
Sample 0 No:
for i to do
0: + Si)
end for
v < 3b - V v ((b, 04,0%
end while
We present the resulting training technique in Algorithm I This algorithm can be used learn a distribution over initializations that minimizes the upper bound presented in Theorem 3 and its specializations. This is presented for the case when A is Bus uniformly stable for some Bus- For gradient-basse based algorithms, the learning rate often appears directly in the bound for 3us 12 Thus is potentially beneficial to update a as well. We present Algorithm | without learning the learning rate. To meta-learn the learning rate, we can augment th to include parameterization of prior distribution over learning rates and update using the same gradient step presented in [ for v.
Determining the gradient of Bb 86, .....,,,00 8)) with respect to 16 requires computing the Hessian of the loss function if algorithm A(B,S) S)) uses gradient update compute 8.. First order approximations
often perform similarly to the second-order meta-learning techniques 227 25 47 and can be used
speed up the training. Additionally, Algorithm can be modified to use mini-batches of tasks instead of all tasks in the meta update to improve training times; we present an algorithm which uses mini-batches of tasks in Appendix A.S.T.
In practice, we are interested in algorithms such as stochastic gradient descent (SGD) and gradient descent (GD) for the base learner. We can obtain bounds on the uniform stability constant Sus when using gradient methods with the results from [29]. See Appendix A.4 for details on the Bus bounds use in this work. With a bound on Bus, we can calculate all the terms in B(eb, 8 82 ..., 8)) and use Algorithm to minimize the meta-learning upper bound. When evaluating the upper bound, we use the sample convergence bound 37 24 Appendix A.6 for details.
upper bound the expectation taken over 0 Pa. See
Examples
We demonstrate our approach on three examples below, All examples we provide are few-shot meta- learning problems. To adapt at the base level, m examples from each class are given for an "m-shot" learning problem. If applicable, samples can be given validation data for each task during the meta-training step. the first two examples, our primary goal to demonstrate the tightness of our generalization bounds compared to other meta-learning bounds. We also present empirical test performance on held-out data; however, we emphasize that the focus of our work is to obtain improved generalization guarantees (and not necessarily to improve empirical test performance). In the third example, we present an algorithm that is motivated by our theoretical framework and demonstrate its ability improve empirical performance challenging task. All the code required to run the following examples is available at /tttps:/gitthe com/ iiroi-oo----// waarroo-aabbaee 1ab//aaaaaaaaaa Pt0//AAC-BSSSS BUS
5.1 Example: classification on the unit ball
We evaluate the tightness of the generalization bound in Equation 2 on a toy two-class classification problem where the sample space Z is the unit ball (0, 1) in two dimensions with radius I and centered at the origin. Data points for each task are sampled from Patt, where a task corresponds to particular concept which labels the data as (+) if within B²(c,, rı) and (-) otherwise. Center c is sampled uniformly from the y 2 0 semi-ball B (0, 0.4) of radius 0.4. The radius r, is then sampled uniformly from [0.1, - [|]]]]] Notably, the decision boundary between classes nonlinear.
Thus, generalization bounds which rely convex losses (such as [34] will have difficulty with
7

---

Table I: We present the generalization bounds (for 5 0.01) provided by each method if applicable, and use the sample convergence bound [37] for MR-MAML, and PAC-BUS, but not MLAP-M." Note that for these methods, we specifically minimize their respective meta-learning bounds. We also report the meta-test loss (the softmax activated cross-entropy loss - .EL,,) for all methods. We present the mean and standard deviation after 5 trials. We highlight that our approach provides the strongest generalization guarantee.
Classification on Ball
MAML
25
MLAP-M S
MR-MAML 1
PAC-BUS (ours)
Bound
None
1.0538 + 0.0012
0.3422 1 0.0006
0.2213 + 0.0012
Test Loss
0.1701 1 0.0070
0.1645 1 0.0045
0.1584 = 0.0012
0.1657 + 0.0014
providing guarantees for networks that perform well. We choose the softmax-activatee cross-entropy loss, CEL,, as the loss function. Before running Algorithm D1 we address few technical challenges that arise from Assumption 1 as well as computing er, and cg. We address these in Appendix A..5
We then apply Algorithm 1 using the few-shot learning bound in Inequality D We present the guarantee on the meta-test loss associated with each training method in Table [ In addition,
present the average meta-test loss after training with 10 samples. We compare our bounds and empirical performance with the meta-learning by adjusting priors (MLAP) technique [5] and the meta-regularized MAML (MR-MAML) technique [77]. All methods are given held-out data to learn prior before minimizing their respective upper bounds (see Appendix 1. for further details on the prior training step). Additionally, since all bounds require the loss to be within [0. 1]. networks N are constrained such that the Frobenius norm of the output is bounded by r. i.e., [[ || I r. We compare the aforementioned methods' meta-test loss to MAML with weights constrained in the same manner (note that MAML does not provide guarantee). Upper bounds which use the PAC-Bayes framework are computed with many evaluations from the posterior distribution. This allows us to apply the sample convergence bound 37
(as in Equation (5) for our bound) unless otherwise noted.
We find that PAC-BUS provides a significantly stronger guarantee compared with the other methods. Note that the guarantee provided by MLAP-M (5) is vacuous because the meta-test loss is bounded between 0 and 1, while the guarantee is above 1.
5.2 Example: Mini-Wiki
Next, we present results on the Mini-Wike benchmark introduced in 34] This is derived from the Wiki3029 dataset presented ( The dataset is comprised of 4-class, m-shot learning tasks with sample space 2 = {= E Te | 1). Sentences from various Wikipedia articles are passed through the continuous-bas bassss-a--f----- oo-dorss GloVe embedding [5T] into dimension
50 to generate samples. For this learning task, we use k-class version of CEL, and logistic regression. Since this example is convex, we can use GD and bound Bus with Theorem in the appendix [29]. We keep the loss bounded by constraining the network || (z)]lz < r and scale the loss in the previous example. The tightness of the bounds on CL and cg affected the upper bound in Inequality more than in the previous example, we bound them tightly possible. See Appendix A.9 for the calculations.
We apply Algorithm | using the bound which allows for validation data, Inequality to learn on 4-way Mini- Wiki m = {1,3, 5s-hhot. The results are presented in Table 2 We compare our results with the FMRL variant which provides a guarantee [44) follow-the-last-iteral
(FI.I)-Batch, and with MR-MAML (77]. FLI-Batch does not require bounded losses explicitly, but requires that the parameters of the network lie within ball of radius For the logistic regression used in the example, this is equivalent to [NN S r. Thus, we scale the loss and use the same r for each method to provide fair comparison. We also show the results of training with MAML constrained in the same way for reference. Each method is given the same amount of held-out data for training a prior (see Appendix 1.. for further details training the prior).
2 "Due to high computation times associated with estimating the MLAP upper bound, this value not computed with the sample convergence bound as the other upper bounds are. Thus, the value presented does not carry a guarantee, but would be similar if computed with the sample convergence bound. The value is shown to give a qualitative sense of the guarantee.
8

---

We compare the generalization bounds (for 8 0.01) provided by each method where appli- cable and use the sample convergence bound for MR-MAML and PAC-BUS. Since we specifically minimize these methods upper bounds, we can fairly compare the relative tightness of each bound. We also report the meta-test loss (CEL..) ) for each method for exposition. We report the mean and standard deviation after 5 trials. We highlight that our approach provides the strongest guarantee.
Table 2:
4- Way Mini- Wiki
1-shot +
3-shot
5-shot
FLI-Batch Bound
0.6638 + 0.0011
0.6366 + 0.0006
0.6343 0.0014
MR-MA PR-MAAL Bound
0.7400 + 0.0003
0.7312 0.0003
0.7283 0.0005
PAC-BUS Bound (ours)
0.4999 + 0.0003
0.5058 + 0.0002
0.5101 + 0.0002
MAML 2
0.3916 + 0.0009
0.3868 + 0.0005
0.3883 + 0.0005
FLI-Batch
0,4091 + 0.0008
0,4078 + 0.0005
0.4097 = 0.0012
MR-MAML 7ir
0.3922 + 0.0009
0.3869 + 0.0003
0.3884 0.0005
PAC-BUS (ours)
0.3922 + 0.0009
0.3878 + 0.0003
0.3895 0.0005
As in the previous example, PAC-BUS provides a significantly tighter guarantee than the other methods (Table 2 We see similar empirical meta-test loss for MAML [25). MR-MAML [77], and PAC-BUS with slightly higher loss for FLI-Batch [34]. In addition, we computed the meta-test accuracy as the percentage of correctly classified sentences. See Table 2 in Section A. 11.2 for these results along with other experimental details.
5.3 Example: memorizable Omniglot
We have demonstrated the ability of our approach to provide strong generalization guarantees for meta-learning in the settings above. We now consider more complex setting where we are unable to obtain strong guarantees. In this example, we employ a learning heuristic based on the PAC- BUS upper bound, PAC-BUS(H); see Appendix A..5.2 for the details and the Algorithm. We relax Assumption and no longer constrain the network as in previous sections. Instead, we maintain and update estimates of the Lipschitz and smoothness constants of the network, using [83, and incorporate them into the uniform stability regularizer term, Bus. We then scale each regularizer term Å and X2 respectively. Analogous to the technique described in 77. we aim to incorporate the form of the pneoretically-derivee regularizer into the loss, without requiring it to be as restrictive during learning. The result is a regularizer that punishes large deviation from the prior Po.o and too much adaptation at the base-learning level.
(i.e., RPAC-B(Pa, (Po. Po.o. 5, I) and fus) by hyper-parametee
35 for 20-way, m = {1. 5..5)-sho 5)-shot classification in the non-mutually the problem of memorization in meta-learning is explored and demonstrated with non- non-muu exclusive learning problems. NME Omniglot corresponds to randomization of class labels for task at test time only. This worsens the performance of any network that memorized class labels; see 777 for more details. 3 We compare our method to an analogous heuristic presented in (77), which also has a ( Po.o) term in the loss. Thus, this heuristic (referred as MAMMM)))(W) (77) regularizes the change in weights of the network. Additionally, we compare to the heuristic described in 3E (FLI-Online) which performs better in practice than the FLI-Batch method. We do not provide data for training a prior in this case since we do not aim to compute a bound in this example. We use standard MAML as reference. See Table 3 for the results.
We test our method on Omniglot exclusive (NME) case 77. In
We see that MAML 2 and FLI-Online 34 do not prevent memorization on NME Omniglot [77]. This is especially apparent in the 1 1-shot learning case, where their performance suffers significantly due to this memorization. Both MR-MAML(WW) PAC-BUS(H) outperforming MR-MA MR-MAMI Note that PAC-BUS(H) outperforms MR-MAML by a wider margin in the --shot case as compared with the 5-shot case. We believe this is due to the effectiveness of the uniform stability regularizer at the base level. MR-MAML suffers more in the 1-shot case because over-adaptation is more likely with fewer within-task examples.
M and PAC-BUS(H) prevent memorization, with
Conclusion and discussion
We presented a novel generalization bound for gradient- based meta-lcarning: PAC-BUS. We use different generalization frameworks for tackling the distinct challenges of generalization at the two
We slightly different task setup the one in 77 see Appendix A.11.3 for the details of our setup.

---

Table 3: We present the meta-test accuracy as percentage on non-mutually-exxluse Omniglot [77].
In contrast to the previous examples, here we aim achieve the best empirical performance for each method. In particular, this task compares each methods' ability to prevent memorization. We report the mean and standard deviation after trials.
20- WAY Omniglot
NME 1-SHOT 1
NME 5-SHOT 1
MAML 25
23.4
75.1 1.1:46 4.8
FLI-ON -NLIINE
22.4 0.5
39.1 + 0.5
MR- MR-MAML(W)
84.2 + 2.2
94.3 + 0.3
(OURS)
87.9 + 0.5
95.0 0.9
levels of meta-learning. In particular, we employ uniform stability bounds and PAC-Bayes bounds at the base- and meta-learning levels respectively. On a toy non-convex problem and the Mini- Wiki meta-learning task 34. we provide significantly tighter generalization guarantees as compared to state-of-the-ate meta-learning bounds while maintaining comparable empirical performance. To our knowledge, this work presents the first numerically-cvaluaae with proposed meta-learning bound. On memorizable Omniglot (35 777. we show that a heuristic based on the PAC-BUS bound prevents memorization of class labels in contrast to MAML [25], and better performance than neta-regularized MAML mi We believe our framework is well suited to the few-shot learning problems for which we present empirical results, but our framework is potentially applicable to a broad range of different settings (e.g., reinforcement learning).
generalization guarantees associated
We note few challenges with our method motivation for future work. Our bound is vacuous on larger scale learning problems such as Omniglot. This is partially caused by a larger KI-- divergence term in the PAC-Bayes bound when using deep convolutional networks (due to the increased dimensionality of the weight vector). In addition, we do not have theoretical analysis on the convergence properties of the algorithms presented, so we must experimentally determine the number of samples required for tight bounds. In the results of Section 5.1 and 5.2 despite an improved bound over other methods, our method does not necessarily improve empirical test performance. We emphasize that our focus in this work was on deriving stronger generalization guarantees rather than improving empirical performance. However, obtaining approaches that provide both stronger guarantees and empirical performance is an important direction for future work.
Future work can also explore ways in which incorporate tighter PAC-Bayes bounds or those with less restrictive assumptions. One interesting avenue is to extend PAC-BUS by using a PAC-Bayes bound for unbounded loss functions for the meta-generalizztion step (e.g. as presented in 2S Another promising direction is to incorporate regularization on the weights of the network directly (e.g.. L2 regularization or gradient clipping) to create networks with smaller Lipschitz and smoothness constants. Additionally, it would be interesting to explore learning of the base-learner's 's algorithm while maintaining uniform stability. For example, one could parameterize a set of uniformly stable algorithms and learn posterior distribution over the parameters.
Broader impact. The approach we present in this work aims strengthen performance guarantees for gradient-based meta-learning. We believe that strong generalization guarantees in meta-learning. especially in the few-shot learning case, could lead to broader application of machine learning in real-world applications. One such example is for medical diagnosis, where abundant training data for certain diseases may be difficult obtain. Another example on which poor performance is not an option is any safety critical robotic system, such as ones which involve human interaction.
Meta- Mletanleannigg methods typically require lot of data and training time, and ours is not exception. In our case, it took multiple weeks of computation time on Amazon Web Services (AWS) instances to train and compute all networks and results we present in this paper. This creates challenges with accessibility and energy usage.
Acknowledgments
The authors are grateful to the anonymous reviewers for their valuable feedback and suggestions, and to Thomas Griffiths for helpful feedback on this work. The authors were supported by the Office of Naval Research Google Faculty Research Award, and the Amazon Research Award.
N00014 4- 1-81-1-28871) the NSF CAREER award (2044149), the
10

---

References
[1] Karim Abou-Moustafa and Csaba Szepesvári. An Exponential Efron-Stein Inequality for La Stable Learning Rules. Proceedings of the 30th International Conference Algorithmic Learning Theory, 2019.
[2] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-66) 60, 2018.
[3] Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret Bounds for Lifelong Learning. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
[4] Amiran Ambroladze, Emilio Parrado-herándezz, and John Shawe-taylor. Tighter PAC-Bayes Bounds. Advances Neural Information Processing Systems 19, 2007.
[5] Ron Amit and Ron Meir. Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory. Proceedings of the 35th International Conference Machine Learning, 2018.
[6] Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
[7] Sebastien Arnold, Praateek Mahajan, Debajyoti Datta, Ian Bunner, and Konstantinos Saitas Zarkias. learn2learn: A library for meta-learning research. arxiv preprint. preprini arXiv:2008. 12284, 2020.
[8] Sanjeev Arora, Rong Ge. Behnam Neyshabur, and Yi Zhang. Stronger Generalization Bounds for Deep Nets via a Compression Approach. arXiv preprint arXiv:1802.05200 2018
[9] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A Theoretical Analysis of Contrastive Unsupervised Representation Learning. Proceedings of the 36th International Conference on Machine Learning, 2019.
[10] Peter L. Bartlett, Dylan Foster, and Matus J Telgarsky. Opectrally-Normallii Margin Bounds for Neural Networks. In Advances in Neural Information Processing Systems 30, pages 2017.
[11] Samy Bengio, Yoshua Bengio, Jocelyn Cloutier, and Jan Gecsei. On the Optimization of Synaptic Learning Rule. Proceedings of the Conference on Optimality in Artificial and Biological Neural Networks, pages 6-8, 1992.
[12] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth, Occam's Razor. Information Processing Letters, 24(6):377-380, 1987.
[13] Léon Bottou and Vladimir Vapnik. Local Learning Algorithms. Neural Computation, 888-900, 1992.
[14] Olivier Bousquet and André Elisseeff. Stability and Generalization. Journal of Machine Learning Research, 2:499-526, 2002.
[15] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper Bounds for Uniformly Stable Algorithms. Proceedings of the 33rd Conference Learning Theory, 2020.
[16] Rich Caruana. Multitask Learning. Machine Learning, 28:41-75, 1997.
[17] Olivier Catoni. Statistical Learning Theory and Stochastic Optimization. École d'éué de Probabilités de Saint-Flour 2001. Springer, 2004.
[18] Olivier Catoni. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, volume 56 of Lecture notes Monograph Series. Institute of Mathematical Statistics, 2007.
[19] Alain Celisse and Benjamin Guedj. Stability Revisited: New Generalisation Bounds for the Leave-one- Out arXiv preprint 1608v 2016.
[20] Andrew Collette. Python and HDF5. O'Reilly, 2013.

---

[21] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, 2012.
[22] Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-Within-
Online Meta-Learning. Advances in Neural Information Processing Systems 32, 2019. Within-
[23] Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddedd modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[24] Gintare Karolina Dziugaite and Daniel M. Roy. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. Pro- ceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, 2017.
[25] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks. Proceedings of the 34th International Conference on Machine Learning, 2017.
[26] Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. PAC-Bayesian Learning of Linear Classifiers. In Proceedings of the 26th International Conference on Machine Learning, pages 353-360. ACM, 2009.
[27] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adver- sarial Examples. Proceedings of the 3rd International Conference on Learning Representations, 2015.
[28] Maxime Haddouche, Benjamin Guedj, Omar Rivasplata, and John Shawe-Taylor. PAC-Bayes Unleashed: Generalisation Bounds With Unbounded Losses. arXiv preprint arXiv:2006.07279, 2020.
[29] Moritz Hardt, Benjamin Recht, and Yoram Singer. Train Faster, Generalize Better: Stability of Stochastic Gradient Descent. Proceedings of the 33rd International Conference Machine Learning, 2016.
[30] Elad Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimiza- lion, 2(3-4):157-325, 2016.
[31] Tom Heskes. Solving Huge Number of Similar Tasks: a Combination of Multi-Task Learning and a Hicrarchical Bayesian Approach. Proceedings of the 15th International Conference on Machine Learning, 1998.
[32] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-Learning in Neural Networks: A Survey. arXiv preprint arXiv:2004.000 05439, 2020.
[33] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishman, and Samy Bengio. Fantastic Generalization Measures and Where to Find Them. Proceedings of the 8th International Conference on Leurning Representations, 2020.
[34] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Provable Guarantees for Gradient- Based Meta-Learning. Proceedings of the 36th International Conference on Machine Learning, 2019.
[35] B. Lake, R. Salakhutdinov, J. Gross, and J. Tenenbaum. One Shot Learning of Simple Visual Concepts. Cognitive Science, 33, 2011.
[36] John Langford. Tutorial on Practical Prediction Theory for Classification. Journal of Machine Learning Research, 6(Mar):273-300 2005.
[37] John Langford and Rich Caruana. (Not) Bounding the True Error. Advances in Neural Information Processing Systems 14, 2002.
[38] John Langford and John Shawe-Tayle Taylor. PAC-Bayes & margins. Advances in Neural Information Processing Systems 15, 2003.
[39] Ben London. A PAC-Bayesian Analysis of Randomized I Learning with Application to Stochastic Gradient Descent. Advances in Neural Information Processing Systems 30, 2017.
12

---

[40] Andreas Maurer. A Note on the PAC Bayesian Theorem. arXiv preprint arXiv:0411099, 2004.
[41] Andreas Maurer. Algorithmic Stability and Meta-Learning Journal of Machine Learning Research, 6:967-9944 994, 2005.
[42] David McAllester. A PAC-Bayesian Tutorial with A Dropout Bound. arXiv preprint 1rXiv:1307.2118, 2013.
[43] David A McAllester. PAC- AAC-Bayesian Model Averaging, Proceedings of the 12th Conference on Learning Theory, 1999.
[44] MOSEK ApS. Mosek fusion api for python 9.0.105, 2019. URL https://docs. /ww.//kkcc..oo.....o.mm/m/o com/ html
9. wwwpthoonfsiion/onoooooooo
[45] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A PAC- Bayesian Approach to Spectrally-Normalizee Margin Bounds for Neural Networks, preprint arXiv: 2017.
[46] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring Generalization Deep Learning. In Advances in Neural Information Processing Systems 30, pages 5949-5958, 2017.
[47] Alex Nichol, Joshua Achiam, and John Schulman. On First-Order Meta-Leaming Algorithms. arXiv preprint arXiv: 1803.02999 2018
[48] Emilio Barrado-errándde. Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC- Bayes Bounds with Data Dependent Priors. Journal of Machine Learning Research, 13: 3507-3531, 2012.
[49] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems 32, pages 8024-8035, 2019.
[50] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[51] Jeffrey Pemnington, Richard Socher, and Christopher D. Manning. GloVe: Global Vectors for Word Representation. Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing, 2014.
[52] Anastasia Pentina and Christoph H. Lampert. PAC-Bayesian Bound for Lifelong Learning. Proceedings of the 31st International Conference on Machine Learning. 2014.
[53] Anastasia Pentina and Christoph H. Lampert. Lifelong Learning with Non-i.i.d. Tasks, Advances Neural Information Processing Systems 28, 2015.
[54] María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter Risk Certificates for Neural Networks. arXiv preprint arXiv:2007.12911 2020.
[55] Sachin Ravi and Hugo Larochelle. Optimization as Model for Few-Shot Learning, Proceedings of the 5th International Conference on Learning Representations. 2017.
[56] Jorma Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientific, 1989.
[57] Omar Rivasplata, Emilio Herradd-err.adez.. John Shawe-Taylon Shiliang Sun, and Csaba Szepesvari. PAC-Bayes Bounds for Stable Algorithms with Instance-Dependent Priors. Ad- vances in Neural Information Processing Systems 31, 2018
[58] Omar Rivasplata, Vikram M. Tankasali, and Csaba Szepesvari. PAC-Bayes with Backprop. arXiv preprint 1rXiv:1908.07380, 2019, 2019.
13

---

[59] Omar Rivasplata, Iija Kuzborskij. Csaba Szepesvari, and John Shawe-Taylor. PAC-Bayes Analysis Beyond the Usual Bounds. Advances in Neural Information Processing Systems 33, 2020.
[60] Jonas Rothfuss, Vincent Fortuin, and Andreas Krause, PACOH: Bayes-Optimal Meta-Learning with PAC--uarantees. arXiv preprint arXiv:2002.05551, 2020.
[61] Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap. Meta-Learning with Memory-Augmenter Neural Networks. Proceedings of the 33rd Interna- tional Conference on Machine Learning, 2016.
[62] Jurgen Schmidhuber. Evolutionary Principles in Self-Referential Learning. On Learning how to Learn: The Meta-Meta-Metta.-Hoood Diploma thesis, Technische Universitat Munchen, Germany, 1987.
[63] Rolf Schneider. Convex Bodies: The BrinonMinkowski Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 2013.
[64] Matthias Seeger. PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classifica- tion. Journal of Machine Learning Research, 3(Oct):233-265 2002.
[65] Shai Shalev-Shwartz and Shai Ren-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[66] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, Stability and Uniform Convergence. Journal of Machine Learning Research, 1 11:2635-2670, 2010.
[67] John Shawe-Taylor and Robert C. Williamson. A PAC Analysis of Bayesian Estimator. Proceedings of the 10th Conference on Computational Learning Theory, 1997.
[68] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying Some Distri- butional Robustness with Principled Adversarial Training. arXiv preprint arXiv:1710.10571, 2020.
[69] Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A Strongly Quasiconvex PAC-Bayesian Bound. Machine Learning Research, 76:1-26, 2017.
[70] Sebastian Thrun and Lorien Pratt. Learning to Learn. Springer Science & Business Media, 1998.
[71] Vladimir N. Vapnik and A. Ya Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Dokl. Akad. Nauk, 181(4), 1968.
[72] Ricardo Vilalta and Youssef Drissi. A Perspective View and Survey of Meta-Learning Artificial Intelligence Review, 18:77-95, 2002.
[73] Silvia Villa, Lorenzo Rosasco, and Tomaso Poggio. On Learnabiiity, Complexity and Stability. In Empirical Inference, pages 59-69. Springer, 2013.
[74] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching Networks for One Shot Learning. Advances in Neural Information Processing Systems 29, 2016.
[75] Jeremy Watt, Reza Borhani, and Aggelos K. Katsaggelos. Machine Learning Refined: Founda- tions, Algorithms, and Applications. Cambridge University Press, 2016.
[76] Wolfram Research, Inc. Mathematica, Version 12.0, 2019. URL httpss:/www.www wolfram Com/nathematica/ Champaign, IL.
[77] Mingzhang Yin, George Tucker, Mingyuan Zhou, Sergey Levine, and Chelsea Finn. Meta- Learning without Memorization. Proceedings of the 8th International Conference on Learning Representations, 2020.
[78] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan Adams, and Peter Orbanz. Nonvacuous Generalization Bounds at the ImageNet Scale: PAC-Bayesian Compression Approach. Proceedings of the 7th International Conference on Learning Representations, 2019.
14


Reviews:
[{"review_id": "n-NI6uC5s8b", "reviewer": "Reviewer_Q1zC", "summary": "The paper proposes a generalization bound for meta-learning based on the following PAC frameworks: Uniform Stability for assessing the generalization of the base (task-specific) models to unseen data, and PAC-Bayes for estimating the generalization of the meta-learner to unseen tasks.\nThis implies the use of a stochastic meta-learner, that provides the distribution from which base models are sampled for initializing the task learner.\nThe obtained bound is then tightened for the few-shot learning context, by accounting for additional validation data.\nThe derived bound is finally used as objective function for optimizing the posterior model distribution by stochastic gradient descent, for the particular case of Gaussian posterior and prior distributions and using the reparameterization trick. ", "questions": "", "limitations": "", "rating": 6, "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": "The paper's contributions build on works on bi-level generalization guarantees. To the best of my knowledge, the combination of uniform stability and PAC-Bayes frameworks is new in the meta-learning literature.\n\nThe paper is generally well written, but two key points should be clarified:\n\n1. The notion of uniform stability is used to derive a generalization guarantee in expectation, contrary to the original result from Bousquet which is a PAC guarantee, hence standing with a certain probability. \nThis is a key aspect of the approach and should be highlighted, as it allows to derive the bound of Theorem 3 for meta-learning without using a union bound. Indeed, as highlighted in the paper relying on a union bound for deriving the generalization guarantees is a disadvantage of existing works, as it results in looser guarantees.\nI would also suggest to explicitly report in the theorems the parameters on which \\beta_{US} depends, in order to make it easier for the reader to assess the bound. \n\n2. In Algorithm 1, the posterior's mean and variance are updated via a Monte Carlo estimate of the expected loss, by drawing a model per task to then update it with the base-learner algorithm and to be used to estimate the bound. However I believe that this procedure is unbiased only if the base-learner algorithm is differentiable and jointly optimized with the posterior. It is not clear if this is the case in the proposed optimization procedure.\n\nThe main downside of the derived bounds is that the convergence of the PAC-Bayesian complexity terms explicitly depends only on the number of tasks and not on the sizes of the task samples. This is a source of vacuity on real problems, as the number of tasks is usually small. \nIndeed, in the experiments with the Omniglot dataset of the paper, the complexity term has to be reduced by using smaller models and by down-scaling it.\nA simple (but limited) improvement could be achieved by using PAC-Bayesian bounds with faster convergence rate, such as Seeger's bound [Seeger][Maurer].\n\nFinally, in the experimental evaluation, it would be useful to report also the test error of a model trained on each task singularly (averaged over all the tasks). This would be a valuable sanity check, to make sure that the proposed meta-learning algorithm does not degrade the baseline performance.\n\n### Minor:\nIn Table 2 PAC-BUS bound increases when the number of points m increases. Shouldn't it be the reverse?\n\n[Seeger] PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification, JMLR, 2002.\n\n[Maurer] A note on the PAC Bayesian theorem, 2004\n\n### UPDATE\nThe authors addressed well my questions, but after reading also the other reviews I am still not sure whether recommending acceptance or rejection of the paper, and I am keeping my initial rating of 6. The work improves upon state-of-the-art generalization guarantees for meta-learning and in particular in the few-shot learning context and the paper is well written. However, I still have the following concerns:\n\n1. the novelty of the contributions is limited, as the proposed bound is a modification of works by [Pentina et al.] using (known) stability results at the base-level instead of a PAC-Bayes guarantee;\n2. the practical impact of the bound itself is also limited as at the meta-level it depends only on the number of tasks; this is an intrinsic problem of bi-level guarantees, and the solutions proposed by the authors can only marginally alleviate it.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "k8Upen59sV8", "reviewer": "Reviewer_mTwB", "summary": "This submission is about generalization bounds for gradient-based meta-learning algorithms. It is motivated by the observations that meta-learning algorithms have demonstrated promising empirical results in a variety of tasks, while our theoretical understanding of these algorithms is lagging behind and in particular the existing generalization bounds for meta-learning are challenging to compute or give vacuous values even in simple settings.\n\nI like how this work reasons about the challenges in generalization for meta-learning. The reasoning is by separately considering generalization at the base level and generalization at the meta level, and how the two levels must be coupled. The work proposes to rely on uniform stability to reason about generalization at the base level, and to use PAC-Bayes bounds to reason about generalization at the meta level. The claimed main contribution is that this approach leads to a novel generalization bound (Theorem 3) for gradient-based meta-learning, which is then leveraged to develop a learning method (PAC-BUS) by using the bound as optimization objective, and the method is evaluated in two meta-learning problems. It is not too clear to me how the two levels are coupled to learn the inductive biases that can be used for future tasks, but I suspect that the PAC-Bayes prior must play a role in connecting the two levels.\n\nThe argument behind the proof of the main result (Theorem 3) appears to consist of three blocks: (1) writing the distribution that generates data sets of a given size $m$ as a product distribution between the random tasks and the random samples for given tasks; (2) using the classical PAC-Bayes bound of McAllester for bounding the expected loss (expectation over data sets and over parameters) in terms of its empirical counterpart (that sums over the training tasks) plus a KL regularization term; and (3) using Uniform Stability for bounding the expected loss on a given task in terms of its empirical counterpart and stability. However, I missed an outline of the proof or indication of where the reader can see the full details of the proof.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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\nGeneralization bounds for meta-learning have been proposed before. There are stability-based approaches (works of Maurer) and approaches that are based on PAC-Bayes bounds (Amit and Meir). However, the combination of these two approaches seems to be a novel idea.\n\nSIGNIFICANCE\n\nAssuming that the main result is correct, this is an interesting result conceptually and potentially also with respect to the improved tightness of the numerical bound values that it may lead to in practice. However, I would like to flag that the details of the proof are not provided, nor is the proof outlined at least. I would like to request the author(s) to include in their response an outline of the proof of Theorem 3, and in case this paper is accepted, the author(s) should include such outlined proof in the paper and an additional appendix giving the full details of the proof.\n\nCLARITY / QUALITY / READABILITY\n\nThe paper is relatively well-written. The introduction is very nice and informative. However, I have some concerns regarding Section 2 on problem formulation, where the mathematical language is declared. It seems to me that the choices of notation affect the clarity/readability of the paper in a non-trivial way. I have made an effort to point out specific difficulties that I encountered and to suggest possible fixes. Many other comments of editorial nature are shared next.\n\nEDITORIAL FEEDBACK\n\nTitle: Would the authors consider the title \"Meta-Learning Bounds via PAC-Bayes and Uniform Stability\" ?\n(The acronym PAC-BUS can be introduced and used in the paper.)\n\nL.8-9: \"the result of this approach is a novel PAC bound [...]\" (i.e. insert \"of this approach\" and remove the hyphen)\n\nL.19: Replace \"one\" with \"a learner\" \n\nL.23: \"base learner\" (no hyphen, I think)\n\nL.36: Replace \"realistic problems\" with \"benchmark problems\" and also delete \"ImageNet-scale\"\n\nL.43: \"meta-learner\" (twice)\n\nL.48: Together with [11] it would be good to cite Bousquet et al. (2020) \"Sharper bounds for uniformly stable algorithms\"\n\nL.50-51: I think the definition of \"uniform stability\" of Bousquet & Eliseeff [11] is in the sup norm (hence it makes sense that they called it \"uniform\"), while the definition of Hardt et al. [22] is in expectation (the L_1 norm of the difference) only. Since these two definitions do not coincide, this passage is potentially confusing/misleading without further clarification. Perhaps say that [22] demonstrated that limiting the number of training epochs [...] leads to stability in expectation.\n\nL.52: delete \"uniformly\"\nL.54: delete \"uniform\"\n\nPossibly the work of Shalev-Shwartz and collaborators (\"Learnability, stability and uniform convergence\" and \"Learnability and stability in the general learning setting\") and perhaps work of Poggio and collaborators (\"On learnability, complexity and stability\") could be cited to support the connection between stability and learnability, on which you rely at the base level?\n\nL.60-61: Replace \"one has seen\" with \"that have been seen\"\n\nL.68-69: \"We refer to the resulting approach as PAC-BUS since it combines PAC-Bayes and Uniform Stability to derive generalization guarantees for meta-learning.\"\n\nSection 2: The math notation choice has an impact on the clarity/readability of the submission. I suggest to choose notation that helps keep concepts clearly distinguishable but at the same time is suggestive in that it makes apparent the connection between related objects, and overall notation that is convenient and easy to follow. As reference I suggest looking e.g. the papers of Andreas Maurer (\"Algorithmic Stability and Meta-Learning\" and \"A Second-order Look at Stability and Generalization\") or the statistical learning literature (papers/surveys by Massart, Boucheron, Lugosi and others) which I consider good examples with regards to the mathematical language that notation that hey use. In particular, I recommend the convention of using capitals (e.g. $X$ or $Y$ or $Z$) to denote random variables, using their lower-case counterparts ($x$, $y$, $z$ respectively) to denote arbitrary possible values of these random variables, and using calligraphic capitals ($\\mathcal{X}$, $\\mathcal{Y}$, $\\mathcal{Z}$) for the sets of all possible values of these variables (i.e. their \"spaces\"). It makes perfectly clear the distinction between the different categories of objects (a random quantity, a fixed but arbitrary quantity, or the set of all possible values, respectively). I also recommend a separate kind of notation for the distributions of random variables, like $P$ (for \"probability\") or $\\mu$ (must come from \"measure\" and is used often to denote a probability measure), and using subscripts for different $P$'s or $\\mu$'s (e.g. $P_t$ or $\\mu_t$ for the distribution of task $t$). Then if needed you could choose suitable notation for the set of all probability distributions over a given space, and so on. \n\nLast note on notation choice: It could be good to make the distinction between expected loss and empirical loss visually apparent, say $L(h,\\mu_t)$ and $\\hat{L}(h,S_t)$ where the \"hat\" in the latter indicates the sample average.\n\nL.124-125: \"More recent frameworks include PAC-Bayes theory [...]\" (since the acronym has been declared before)\n\nL.127: \" [49, 31, 19, 44]\" (i.e. reference [44] belongs in this context as well, as do the works of Parrado-Hernandez et al. (2012) \"PAC-Bayes bounds with data dependent priors\" and Ambrolarze et al. (2006) \"Tighter PAC-Bayes bounds\" arguably.)\n\nL.128: \" [31, 33, 41]\" (i.e. reference [41] is relevant here, which supersedes [45] with respect to tightening the bound values) and for the works that generalize the framework perhaps the list [13, 14] should be enlarged with Rivasplata et al. (2020) \"PAC-Bayes Analysis Beyond the usual Bounds\" at least.\n\nNote that there is an important difference between a citation like [27] for \"FMTL\" and a citation like [23] for \"FTL\" since in the former case \"FMTL\" was introduced in the given citation [27] while in the latter case \"FTL\" existed in the literature before [23]. Hence, to make this difference apparent, I suggest writing \"see e.g. [23]\" if you want to use [23] as a reference for FTL. I am not objecting [23] as a suitable reference to look up the definition of FTL, in fact I believe it is, what I am suggesting is to use \"see e.g.\" in order to signal that [23] is a good place to look up \"FTL\" while there are (many) others. Please make sure this distinction is followed for other references throughout the paper.\n\nL.176: Replace \"by some\" with \"by a copy\" and clarify the distributional assumption of the $z'_i$ for the sake of clarity. Unless these data points are not random. But if $z_1, ..., z_m$ are random, as it sees from the problem formulation (L.86), then it makes sense that   $z'_1, ..., z'_m$ should also be random, and probably they are independent from $z_1, ..., z_m$ but coming from the same distribution.\n\nL.180-182 (Definition 1): I don't see the point of \"differ-by-one\" (nor the corresponding acronym) since there is no other notion of change in the dataset in your paper (i.e. there is no \"differ-by-two\" or \"differ-by-three\"), On the other hand, as is well known, analysing stability to changing two or three data points reduces to analysing change in one data point at a time by the triangle inequality, hence the stability to changing one datapoint is the fundamental notion here. I prefer to read \"Algorithm $A$ is uniformly stable with $\\beta>0$ with respect to a loss $L$ if ...\" and then after Eq.(2) write that you define $\\beta_{US}$ to be the minimal $\\beta>0$ in the right hand side. Since it is specific to algorithm $A$, probably it is even better to define $\\beta_{US}(A)$ as the minimal such $\\beta$. There is something missing in the quantification of variables in this definition, since $z'_i$ are currently not quantified. Also, if this condition is for random $z_1, ..., z_m$ and $z'_1, ..., z'_m$ (i.e. they are random variables) then probably the requirement should be that the inequality holds almost surely. But it looks that your definition wants to require that the inequality holds for any arbitrary $z_1, ..., z_m$ and $z'_1, ..., z'_m$, in which case the notation choice is hot helping to distinguish random variables from the arbitrary values that they may take. [A notation choice that I recommend is using capital letters (e.g. $X$) for a random variable, the corresponding lower-case ($x$) for an arbitrary possible value of this random variable, and capital calligraphic ($\\mathcal{X}$) for the space of all possible values of this random variable. If used consistently, this notation makes it crystal clear what category of object occurs at each place.] In case (as I suspect) this definition is meant to require the inequality for all arbitrary choices of $z_1, ..., z_m$ and $z'_1, ..., z'_m$, it could be more convenient to write Eq.(2) with a supremum on the left-hand side, and clarifying in the next line that the supremum is over all $m$-tuples $(z_1, ..., z_m)$ and $(z'_1, ..., z'_m)$ that differ at one entry, and over the other things ($z$ and $i$ and $\\theta$). Also I'd like to point out that the role of the task $t$ is not apparent in Eq. (2) currently, which needs clarification.\n\nL.183-184: Since there is no citation to which this Theorem 1 is attributed, it could be assumed that you are implying that this theorem is yours? Could be better to write \"The following result [22, Theorem X.Y] establishes a relationship between uniform stability and generalization in expectation.\" (Note that I am suggesting to be explicit about which theorem in [22] you are citing.)\n\nL.188: This is a good place to discus the outline of the proof of Theorem 1, and insert a cross-reference to where the proof is given in full detail. \n\nL.196: Is \"sample $s$\" a single datapoint? Ir is $s$ a list of datapoints? This needs to be clarified. Correspondingly, the distribution $\\mathcal{D}$ should be over the space of a single data point or over some product space for tuples of data points, this needs to be said explicitly for the sake of clarity.\n\nL.199: \"the following holds simultaneously for all\" (i.e. insert \"simultaneously\")\n\nNote that the right hand side of Eq.(6) shows that you are using the form of McAllester's bound with the sharp dependence on the number of examples $l$, and this sharp dependence is due to Maurer (2004) \"A note on the PAC-Bayesian theorem\" (McAllester's bound was similar but with a mildly weaker dependence on the number of examples). On this note, the bound of McAllester that you are implying by Eq.(6) was due to McAllester (1999) \"PAC-Bayesian Model Averaging\" (COLT 1999), while the reference [34] in your list of references is McAllester (1998) \"Some PAC-Bayesian Theorems\" (it appeared first in COLT 1998, and then next year it also appeared in the journal Machine Learning). The point is that the correct year for [34] is 1998. But the bound that you are implying in Eq.(6) is the one given in \"PAC-Bayesian Model Averaging\" (with the sharp dependence on $l$ as per Maurer (2004)).\n\nL.206: I miss the point of defining this marginal distribution $\\mathcal{D}_S$ over datasets of size $m$. Should not such marginal distribution be $\\mathcal{D}^m$ (i.e. the product of $m$ copies of the distribution $\\mathcal{D}$)?\n\nL.209: This line is puzzling. In PAC-Bayes bounds the quantity being bounded is an expectation of a loss of the form $L(h_{\\theta},S)$ where the expectation is over the distribution of $\\theta$ and over the distribution of $S$. In your Eq.(7) the two arguments of this loss are coupled, as both depend on $S$. Please elaborate on how to reason about this? There are some conditional expectations that have not been made explicit? Does the PAC-Bayes bound still hold in this case?\n\nL.215: The assumption is that $0 \\leq L(h,z) \\leq 1$ for any $h$ in the hypothesis space for the given problem, and any $z$ in the example space. The current formulation is unnecessarily overloaded.\n\nL.238-239: The notation \"$s$\" was used for a sample in the previous page, while here in this page it is used for the marginal variance parameters of a Gaussian with diagonal covariance. Could we use a different symbol? Also, it would be good to be explicit about the dimensionality of $\\theta$ and then it will be clear the dimension of the space over which we have these Gaussian distributions.\n\nL.241: Explain the symbol $\\odot$ used in Eq.(10) which I assume is a Hadamard product?\n\nL.251-252: Could the authors provide an appendix with details for the extension to mini-batches of tasks?\n\nL.252-253: \"stochastic gradient descent (SGD) and gradient descent (GD)\"\n\nCaption of Table 1: \"We also report the meta-test loss (CEL_s) for all methods.\"\nAlso, may we see the definition of the acronym CEL (and a suitable reference)?\n\nL.275: \"cross-entropy\" (with hyphen)\n\nL.284: Was this notation declared? May be I missed it, but it would not harm to clarify (write explicit) that N is the neural network and  the norm with subscript F is the Frobenious norm.\n\nL.335-336: Insert a reference to support the claim that \"it may cause memorization\" which refers to learning the prior, was this something reported by [58]? Or if this was something that was observed in your own experiments, then explain this fact with accompanying discussion.\n\nL.345: \"meta-learning: PAC-BUS\" (i.e. replace the comma with a colon)\n\nL.367: What are \"broader PAC-Bayes bounds\"? I did not follow the meaning of \"broader\" in this sentence (while the meaning of \"tighter\" is clear, of course).\n\nL.368-369: \"using a PAC-Bayes bound for unbounded loss functions for the meta-generalization step\"\n\n\nL.296: \"through the continuous-bag-of-words GloVe embedding [38] into dimension d = 50 to generate samples\"\n\nWould like for all my feedback above to be addressed in the author response.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "RGO-FFnQp8", "reviewer": "Reviewer_wSzt", "summary": "The paper provides generalization bounds for meta-learning approaches. The result combines two frameworks: uniform stability of gradient descent based learning algorithms that cover guarantees at the base classifiers level and PAC-Bayes theory for obtaining results at the meta level. The objective is to have bounds that become tighter when the base learner adapts quickly. The framework proposed allows the authors to develop new algorithms and regularization scheme. An experimental evaluation is conducted on a toy problem and standard benchmarks.", "questions": "", "limitations": "", "rating": 6, "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 fewshot learning methods is still challenging and results going in this direction are important. The proposed contribution combines an existing uniform stability framework with a classic version of the PAC-Bayes framework. This is not particular new, the novelty lies here in the application to the fewshot learning framework. \nIn my opinion, the novelty is moderate.\n\n\n\nQuality\n------\nThe global scope is of ok. The authors have completed their claims by complementary results in Appendix.\nI have however the following reservations:\n-The uniform stability framework of (Hardt et al., ICML'16) is initially presented for randomized algorithms, so the validity of the contributions for non randomized models has to be justified. See the remarks in the comments below.\n-The PAC-Bayes term of Eq.(7) includes only the number tasks and does not include the size of the samples.\n-Comparisons to over PB-based frameworks would have strengthened the experimental part.\n\n\nClarity\n------\nThe paper is globally clear.\nFew additional lines for describing a bit clearly the fewshot framework (meta-learning, meta-testing, k-way N-shot) would certainly help an unfamiliar reader to better understand some concepts presented in the paper.\n\n\n\nSignificance\n----------------\nThe basis of the work relies on existing techniques. The result obtained in Thm 3 is relatively direct from the considered frameworks. The contribution represents another step in considering PAC-Bayes for few shot learning, but the result in my opinion is not particularly significant.\nIn particular, the result does not exhibits how the combination between tasks and the number of instances can lead to learn with few examples: even with the increasing number of training data, the number of tasks still need to be important. From the bound, it seems that the number of tasks considered should be very important.    \n\nFrom the practical evaluation, the bounds seem informative, but comparisons to other settings would also be helpful. I guess here that the quality of $\\Theta_0$ is essential and I did not see much details on how to find this initialization, which would also be interesting for reproducing the results.\n\nThm1 and deduced results has to be refined with respect to the correct framework.\n\n\nComments\n------------\n\n-About Thm1: If I am not mistaken, the result in Thm1 coming from (Hardt et al., ICML'16 [22]) is valid for randomized algorithms and then an expectation over A must be added in the definition. Same for Equation 4. So the application to non stochastic algorithms must be better justified.    \n\nIn the paper, the authors consider theequivalent  following definition of stability    \n$$\nsup_{S,S^i} sup_z sup_\\theta [L(h_A(\\theta,S), z) - L(h_A(\\theta,S^i), z)] \\le \\beta_{US},    \n$$\n\nwhile, the definition of (Hardt et al., ICML'16 [22]) corresponds to   \n$$\nsup_{S,S^i} sup_z E_\\theta [L(h_A(\\theta,S), z) - L(h_A(\\theta,S^i), z)] \\le \\beta_{US} \n$$\n\nThe definition considered in the paper implies the definition of (Hardt et al., ICML'16 [22]). I hope this is what the authors expect, but at least a comment on the change of definition should be made.   \n\nHowever, in Thm 2.2 of (Hardt et al., ICML'16 [22]), it is shown that   \n$$\n E_{S,\\theta} L(h_{A(\\theta,S)}, T) \\le E_{S,\\theta} L(h_{A(\\theta,S)}, S) + \\beta_{US}.   \n$$\n\nSo actually, an expectation is missing.   \n\nThis expectation is missing when one wants also to prove Thm3. That being said, a more formal justification of Thm3 (i.e. with a proof) could be useful maybe.   \n\nThe validity of the approach for gradient descent (and not SGD) should also be discussed accordingly.   \n\n\n-Thm2 uses the classic McAllester version. It could be interesting to obtain other frameworks to obtain tighter results that may be more informative for the few-shot learning context\n\n-Equation 7: here, I guess we assume that each sample S_i has the same number of examples. As far as I can understand, the result, the number of examples is not involved in the PAC-Bayes term, which makes this result similar to frameworks using an hyperprior model. \n\n\n-In Table 1: the only PAC-Bayes bound comes from reference [3], but it would be interesting to compare to other PAC-Bayes results.\n\n-l.223-226, distribution D_{S_{ev}} is introduced here but the justification of this distribution is a bit fuzzy. Few additional lines to explain it would be welcomed here.\n\n\n-About the result. Other recent meta-learning frameworks have tried to propose bounds in O(l\\times (m+n)) [Du et al., Few-Shot Learning via Learning the Representation, Provably, 2020; Tripuraneni et al., Provable Meta-Learning of Linear Representations, 2020].  This could be a strong result to obtain such bounds in a Pac-Bayes context. \n\nI also would have appreciated a discussion on the expressiveness of the framework with respect to other PB-settings for fewshot/meta-learning learning, beyond the computational issues: what is more general, less/more expressive, can the proposed framework be derived from existing frameworks by choosing particular hyperprior for example?\n\n-Lines 272-273 \"Notably, this problem is challenging for losses which are convex in the parameters of the network (since the decision boundary between classes is nonlinear)\" - I am not sure to understand the formulation in general, since what matters is non linearity and not especially non-convexity. It maybe easier to have non-linear formulations with non-convex models, but the formulation should be rewritten here.\n\n-In the related work, the authors should consider and discuss the following reference that is one the first mixing the concepts of stability and PAC-Bayes:   \n*Ben London: A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent. NeurIPS 2017.    \nThis is not exactly the same setting, but this paper is important regarding the topic\n\n-In appendix, lines 18-23, about the fact to use the training data is necessary to have guarantees on performance. I may have missed something, but this points seems to require more justification, in particular why not having another validation set is not sufficient? The learned models become independent from S. The bound might be over-optimistic.\nThen for the validity of the PB bound this raises questions because the optimization of \\theta should be justified to not depend on S.\n\n\n-----------  \nAfter rebuttal  \n-----------  \nThe authors did a very important work in order to bring more justification and additional information.\nFrom the feedbacks provided, I am now convinced that the work is correct and of quality.\nAdding a study on the impact of the parameters of algorithm on the bound and the behavior of the model is for me very interesting in the context of the work.\nThe paper needs now to be updated according to the comments provided to improve the clarity of the paper.\nThe reservations on the work, I have are that the potential increasing of the bound when training data increases and the possibility to use large validation sets in a few-shot learning contexts, anyway in a multi-task setting this point would be less important.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some limitations of the approaches in the conclusion, in particular the convergence properties of the algorithms provided.\nThey also provide a section on the broader impact of the work.\n\nThe work proposed in this paper is mainly fundamental and does not imply some direct negative societal impact. Actually, by trying to provide some generalization guarantees, the papers contributes to a better general understanding of the field.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "2-j-8m3ZU0", "reviewer": "Reviewer_dWUk", "summary": "This work introduces a  novel PAC-Bayes bound for gradient-based meta-learning algorithms. This PAC-Bayes bound exploits a previous bound for uniformly stable learning algorithms.  In opposite to previously proposed bounds for meta-learning methods, the bound is non-vacuous in some data sets and much tighter. Authors also show that a heuristic method based on the minimization of the proposed bound leads to novel meta-learning algorithms. ", "questions": "", "limitations": "", "rating": 7, "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": "The theoretical study of meta-learning algorithms is a very relevant topic in machine learning due to the wide range of potential applications. This work proposes a novel PAC-Bayes bounds that builds in two different frameworks to compute performance guarantees: PAC-Bayes theory and uniformly stable algorithms. Although the uniformly stability bound was previously proposed, this connection seems novel to me. \n\nThe paper is very well written and easy to follow despite the technical difficulty of the topic. And the proposed bound is thoroughly evaluated and gives rise to a novel class of bounds that are non-vacuous in some relevant cases. The derivation and evaluation of a novel meta-learning algorithm based on the minimization of the proposed PAC-Bayes bound are also worth noticing. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the paper are discussed as well as the societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and myself all agree on the significance of the results and their interest to the NeurIPS community. The reviews expressed a number of technical concerns which were all addressed satisfactorily by the authors during the discussion phase. If not done already, I would invite the authors to consider revising their manuscript along the many suggestions made by the reviewers.
Decision: Accept (Poster)