Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis
Authors: Qi CHEN
Changjian Shui
Mario Marchand
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: meta-learning
few-shot learning
deep learning

Abstract: We derive a novel information-theoretic analysis of the generalization property of meta-learning algorithms. Concretely, our analysis proposes a generic understanding in both the conventional learning-to-learn framework \citep{amit2018meta} and the modern model-agnostic meta-learning (MAML) algorithms \citep{finn2017model}.
Moreover, we provide a data-dependent generalization bound for the stochastic variant of MAML, which is \emph{non-vacuous} for deep few-shot learning. As compared to previous bounds that depend on the square norms of gradients, empirical validations on both simulated data and a well-known few-shot benchmark show that our bound is orders of magnitude tighter in most conditions.

Generalization Bounds for Meta-Learning: An Information-Theone Analysis
Qi Chen' Université Laval
Changjian Shui Université Laval
Mario Marchand Université Laval
Abstract
We derive a novel information-theoree -hheoreti analysis of the generalization property meta-learning algorithms. Concretely, our analysis proposes a generic under- standing of both the conventional learning-to-learn framework []] and the modern model-agnostic meta learning (MAML) algorithms 2 Moreover, we provide a data-dependent generalization bound for stochastic variant of MAML, which is non-vacuous for deep few-shot learning. As compared to previous bounds that depend on the square norm of gradients, empirical validations on both simulated data and a well-known few-shot benchmark show that the proposed bound is orders of magnitude tighter in most situations.
Introduction
Learning task with limited samples is erucial for real-world machine learning applications, where proper prior knowledge is key component for successful transfer. Meta-I (3) or learning- to-learn (LTL) aims to extract such information through previous training tasks, which has recently re-emerged as important topic.
Modern approaches based on MAML have gained tremendous success by exploiting the capabili- However, many theoretical questions still remain elusive. For
ties of deep neural networks 4 9 instance, in the most popular methods for few-shot learning [10], the sseciipc parameters and meta-parameterr are updated in support (also called meta- meta-train) and query (also called meta- validaaal))) set, respectively. However, the majority existing theoretical results such as |1:44 do not pro- vide formal understanding of such popular practice. Moreover, modern meta-learning approaches have incorporated over-parametenn prer-parameterized deep neural networks, where conducting the theoretical analysis becomes more challenging.
In this paper, we introduce novel theoretical understanding the generalization property meta- learning through an information-thhoretinn perspective [15), Compared with previous theoretical results, the highlights of our contributions are as follows:
Unified Approach We analyze two popular scenarios. 1) The conventional LTL [I], where the meta-parameters and task-specific parameters updated within the same data (referred joint training). 2) The modern MAML-based approaches where the meta-parameters and task specific parameters updated on distinct data (referred alternate training), and for which the existing theoretical analysis is rare.
Flexible Bounds The proposed cettaagcneraiiitiionn error bounds are highly flexible: they algorithm-dependant, data-dependant, and are valid for non-convex loss functions. 1) Specifically, the generalization error bound for soint-training (Theorem 5.1 is controlled by the mutual information
Department of Computer Science and Software Engineering, <qi. cge.. 1@ulaval ca> Department Electrical Engineering and Computer Engineering, <changjian.shhe shui. @ulavallcaa> Department of Computer Science and Software Engineering, cmario.marchane @ ift fft.ulavllcca>
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

between the output of the randomized algorithm and the whole data set. It can cover the typical results of [2 I. which can be interpreted with an environment-eevl and task-level error. In addition, it reveals the benefit of meta learning compared to single task learning. 2) Moreover, the generalization error bound for alternate-training (Theorem 5.2) is characterized by the conditional mutual information between the output of the randomized algorithm and the meta-vall vila--valdatiinn dataset, conditioned on the meta-train dataset. Intuitively, when the outputs of a meta learning algorithm w.r.t. different input data-sets are similar (i.e. the algorithm is stable w.r.t. the data), the eett-generalizztion error bound will be small. This theoretical result is coherent with the recently- pcconty-proposed Chaser loss in Bayes MAML [[6].
Non-vacuous bounds for gradient-based few-shot learning Conventional gradient- basee meta- learning theories heavily rely on the assumption of Lipschitz loss. However, [17] pointed out that this Lipschitz constant for simple neural networks can be extremely large. Thus, conventional gradient- based upper bounds are often vacuous for deep few-shot scenarios. In contrast, we propose a tighter data-depend bound that depends on the expected pradient-incohene
rather than the gradient norm (the approximation of the Lipschitz constant) [18] for the Meta-SGLD algorithm, which is a stochastic variant of MAML that uses the Stochastic Gradient Langevin Dynamics (SGLD) [[9]. We finally validate our theory in few-shot learning scenarios and obtain orders of magnitude tighter bounds in most situations, compared to conventional gradient- based bounds.
2 Related Work
Conventional LTL The early theoretic framework, introduced by Baxter 11 proposed the notion of task environment and derived uniform convergence bounds based on the capacity and covering numbers of function classes. Pentina and Lampert [12) proposed PAC-Bayes risk bounds that depend on environment-level and task-level errors. Amit and Meir [ extended this approach and provided a tighter risk bound. However, their theory applies to stochastic neural networks and used factorized Gaussians to approximate the parameters' distributions, which is computationally expensive to use in practice. Jose and Simeone [20) first analyzed meta-learning through information-theorett tools, while they applied the assumptions that hide some probabilistic relations and obtained theoretical results substantially different from those presented here. Limited to the space, more detailed discussion is provided in Appendix
Gradient based meta-learning In recent years, gradient- graddent-bbseed meta-learning such as MAML 2 have drawn increasing attention since they are -aneo--ggostic and are easily deployed for complex tasks like reinforcement learning, computer vision, and federate learning 221 Then, Reptile 25 provided a general first-order gradient calculation method. Other methods combine MAML and Bayesian methods through structured variational inference (26) and empirical Bayes (27). In Bayes MAMI they propose fast Bayesian adaption method using Stein variational gradient descent and conceived Chaser loss which coincides with the proposed Theorem 5.2
On the theoretical side, Denevi et al. [33 analyzed the average excess risk for Stochastic Gradient Descent (SGD) with Convex and Lipschitz loss. Balcan et al. [4] studied meta-lcarning through the lens of online convex optimization, and has provided a guarantee with a regret bound. Khodak et al. 28 extended to more general settings where the task- muskeenviromment changes dynamically or the tasks share a certain geometric structure. Other guarantees for online meta-learning scenarios are provided by Denevi et al. 22 and Finn et al. [30]. Finally, [3] 32 MAML-based methods.
also provided a convergence analysis for
On meta train-validation split Although the support query approaches are rather difficult to analyze, some interesting works have appeared on the simplified linear models. Denevi al. [33] first studied train-validation split for linear centroid meta-learning They proved a generalization bound and concluded that there exists a trade-off for train-validation split, which is consistent with Theorem 5.2 in our paper. Bai et al. 34 applied the random matrix theoretical analysis for a disentangled comparison between joint training and alternate training under the realizable assumption in linear centroid meta-learning By calculating the closed-form concentration rates over the mean square error of parameter estimation for the two settings, they obtained a better rate constant with joint training. However, we aim to provide a generic analysis and do not make such realizable assumption. We believe an additional excess risk analysis with more assumptions is needed for a similar comparison, which is out of the scope of this article. Morcover, Saunshi et al. [35] analyzed the train- aain-validation

---

split for linear representation learning. They showed that the train-validate validation split encourages learning a low-rank representation. More detailed discussion and comparison can be found in Appendix [F]
Information-theoreti learning for single tasks We use here an intormationnthhoettie approach, introduced by Russo and Zou (36] and Xu and Raginsky [15], for characterizing single-task learning. Characterizing the generalization error of learning algorithm in terms of the mutual information be-
tween its input and output brings the significant advantage of the ability to incorporate the dependence on the data distribution, the hypothesis space, and the learning algorithm. This is in sharp contrast with conventional VC-dimension bounds and uniform stability bounds. Tighter mutual information bounds between the parameters and a single data point are explored in [37]. Pensia et al. [38 applied the mutual- -inormaaifooatnoonn framework to a broad class of iterative algorithms, including SGLD and stochastic gradient Hamiltonian Monte Carlo (SGHMC). Negrea et al. [9 provided data detendepnnd estimates of information-thenet bounds for SGLD. For recent comprehensive study, see Steinke and Zakynthinou 40)
3 Preliminaries
Basic Notations We use upper case letters, e.g. X.Y, to denote random variables and corre- sponding calligraphic letters X. y to denote the sets which they are defined on. We denote as Px. the marginal probability distribution of X. Given the Markov chain X Y, Pyix denotes the conditional distribution or the Markov transition kernel. X IL Y means X and Y are independent.
And let us recall some basic definitions:
Definition 3.1. Let x (A) log EleA(X-E[X]) denote the cumulant generating function( of random variable X. Then X is said to be o-subgaussian we have
X²02
(x(()) S 2 .VER.
Definition 3.2. Let X, Y and 7 be arbitrary random variables, and let DgL. denote the KL. divergence. The mutual information between X and Y is defined as:
I(X;Y) dd Dru(PxylIPxxX
The disintegrated mutual information between X and Y given Z is defined as: (X; dd (Px. 22 Pr12).
The corresponding conditional mutual information is defined as:
I(X;YIZ) dd |2 (x:Y))
Information theoretic bound for single task learning We consider an unknown distribution
on an instance space 2 = X' V, and a of independent samples S [ drawn from Jc: Zi ~ μ and S ~ nt Given a parametrized hypothesis space W and loss function f W x Z + R. the true risk and the empirical risk of E W respectively defined as (w) del Ez=pe((u) , Z) and Rs(w) del (1/m) (
Following the setting of cntermatiionthhhoretie learning 36 15 371.
learning algorithm .A is randomized mapping that takes a dataset 5 as input and outputs a hypothesis W according to Pwis The (mean) generalization error gen(u. A) del (W)) (w)) of an algorithm A is then bounded according to:
conditional distribution Pwis, i.e., W A(S)
Theorem 3.1. (Xu and Raginsky (15 Suppose that for each w E W, the prediction loss E(w, Z) is o-subgaussian with respect to 7, ~ μ. Then for any randomized learner A characterized by Pwis- for S nr we have
20
gen(u, A) <
T(W
I(W; :) the mutual information between the input and output of algorithm A (see definition in Definition A.2). Theorem 3.1 reveals that the less the output hypothesis W depends on the dataset S, the smaller the generalization error of the learning algorithm will be.
NNte that the conditional distribution Pwis is different from the posterior distribution in Bayes learning.
3

---

Problem Setup
assume that all tasks originate from common environment which is probability measure on the set probability measures on 2 = X x y. The draw of p ~ T represents encountering learning task fa in the environment т. To learning algorithm for task, need to draw a set of data samples from μ.. In meta learning, there are multiple tasks, for simplicity, we sample size m. Based Maurer et al. [41] the environment
Following [[I].
assume that each task has the induces a mixture distribution pm., on 2d such that Um,, (A) Epoo [a* (A)], VA C z Thus the m data points in S that are independently sampled from random task j encountered in is denoted as S ~ pm.r.
Consequently, for train tasks that are independently sampled from the environment each train data set is denoted as S Mm.r for é E [n]. Analogously. for test tasks data sets, we denote S Mm., for each i [k:.. We further denote the (full) training set S1.n (S1 ..., Sp) and the (full) testing set as 51sk = (S,, Sk).
Meta Learner & Base Learner
Since different tasks are assumed to be an i.i.d. sampling from they should share some common information. We use meta parameter Wi. (W1.... Wx) the task specific parameters, where each W; E W, Vi [n). By exploring the relations between U and W, we can design different meta learning algorithms. For example, 12 treated U as the hyper-parameters of the base learner that produces W. In gradient based meta-learning such as MAML. [2], U was chosen be an initialization of W (hence, = W) for gradient-descent base learner.
U to represent this shared knowledge. We also denote by
We define the meta learner Ameta an algorithm that takes the data sets S as input, and then outputs a random meta-parameter U Ameta(S
Pu Sum. which is distribution that characterizes Ameta- When learning new task, the base learner Abase uses new data set S Um.. and the estimated meta-parameter U to output a stochastic predictor W Abase (U, Pw
To evaluate the quality of the meta information U for learning a new task, we define the true meta risk, given the base learner Abasc
R2 (U) del Es Bw [R (W)
Joint Training & Alternate Training
Since t and are unknown, we can only estimate U and W from the observed data. Generally, there different types of methods for evaluating meta and task parameters.
S
S
BF
[L
Le [.7]
(a) Joint Training
(b) Altemate Training
Figure I: Parameter updating strategy through noisy iterative approach.
Although the base learner is the same, Pw, U.S, is different for each task due the different data St.

---

For Joint Training [ 12), the whole dataset S1.m is used to jointly evaluate all the parameters (U, Wim) in parallel. similar training protocol illustrated in Fig. la Then the corresponding empirical meta risk w.r.t. U is defined as:
Rs (U) n Ei= Ew,~Pw a,0 [s. (W.)
For Alternate training, used in modern deep meta-learning algorithms [2], S; is randomly split into two smaller datasets: a meta-train set S with | my and a meta-validation set S with ||;9| = Mea examples for each i E [m]. In few-shot learning, S and S1. are denoted as the support set and query set. Additionally, we have m Myr + mya and S S. An example of the training protocol is illustrated in Fig. [b] where (U, Wim) are alternately updated through Si and S Sim respectively. The corresponding empirical mela risk w.r.t U is defined as:
Rs.... (U)
Ewi-Pw, sg.0 [Rs (W;)]
Then, the meta generalization error within these two modes w.r.t. Ameta and Abase are respectively defined as
meta (T, Ameta Abase)
Eu.s... (U) Rs.... (U)),
gen meta
(T, Ametas Abaso)
del EU,,I. in [R, (U) RS (U))
5
Infornation-Theoreii Generalization Bounds
We provide here novel generalization bounds for joint and alternate training, which are respectively characterized by mutual information (MI) and conditional mutual information (CMI). These theo- retical results are valid for any randomized algorithm Ameta and Ansee But for some deterministic algorithms producing deterministic predictors, the mutual information bound can be vacuous.
5.1 Mutual Information (MI) Bound in Joint Training
Theorem 5.1. Suppose all tasks use the same loss ZZZ, w). which is o-subgaussian for each w E W. where Z ~ Hr p ~ T. Then, the meta generalization error for joint training is upper bounded by
20 nm
Igenmiia (T, Amera: Abuse) ) S
I(U, Wim S1m)
The proof of Theorem 5.1 presented in Appendix B.I Moreover, according to the chain rule of the error bound in Theorem 5.1 can be further decomposed as
2 (IUU: S1:n) + E. I(W;; S(U)) S V 2o
mn I(U;
+
2n Σ S.U)
Discussions The first and second terms reflect, respectively, the environmental and task-level uncer- tainty. In the limit of a very large number of tasks (n - oc) and a finite number m of samples per task, the first term converges to zero, while the second term remains non-zero. This is consistent with Theorem 1 of Bai et al. 34 where they proved that joint training has bias in general. However, this non-zero term will be smaller than the mutual information of single-task task learning. Indeed, let I(W:) S) denotes the mutual information of single-task learning, we have, as shown in Appendix B.22 that 5) > I(W;SUU) & E I(W;; (U), which illustrates the benefits of learning the meta-parameter U. 2) When we have a constant number n tasks, while the number m of samples per task goes to infinity, the whole bound will converge to zero. Note that the meta generalization error bound reflects how the meta-informmtion assists a new task to learn. If the new task has a sufficiently large number of samples, the generalization error will be small, and the veta-information U does not significantly help learning the new task.
Relation with previous work Since mutual information implicitly depends on the unknown distribu- tion r, it hard to estimate and minimize [42]. By introducing an arbitrary distribution free prior Q on 24 x W we can upper bound I [U, W1 S1:n) S [UU, W1s:: S1mn) + D (Pk(PP,,ve Pu.. |[Q) Esi., D 1St., [[Q) (see Lemma A 1). If we set a joint prior Q = P I[ P. then the bound of Theorem becomees similar to the one proposed by [I. where P is the hyper-prior and P the task-prior in their settings. Finally, note that the bound of Theorem 5.1 tighter than the one
proposed by [12]. where the KL divergence is outside of the square root function.
5

---

5.2 Conditional Mutual Information (CMI) Bound for Alternate Training
Theorem 5.2. Assume that all the tasks use the same loss function E(Z, w), which is o-subgaussian for each w E W, where Z v μr p on T. Then we have
20 1 S mm (U, Wimi Lin
20 IQU
Wims S S
Igen
meta (T, Amera Abaw)) S B
lin
See the proof in Appendix B.3 The second inequality is obtained with the Jensen's 's inequality for the concave square root function and Lemma A. Additionally, we can apply the chain rule on the conditional mutual information, obtain the following decomposition:
I(U, Win ST. (Tmm) = [(U; S1.m (TT..) + Ei= 5,
Es... DKL (Pris.... .. P (
Eu,s... Ei=1 DRL
Discussions The aforementioned decomposition reveals the following intuition: Suppose the outputs of the base learner and meta learner w.r.t. different input data-sets are similar (i.e. the learning algorithms are stable w.r.t the data). In that case, the metta-eenealliztionn error bound will be small. Moreover, since the bound of Theorem 5.2 is data-dependent w.r.t. Si.,. we can obtain tighter theoretical results through these data-dependent estimates. This is to be contrasted with the mutual information bound of Theorem 5.1] which depends on the unknown distribution and can thus be inflated through the variational form. In Sec [6] we analyze noisy iterative algorithms in deep few-shot learning to obtain tighter estimates. Besides, there exists an inherent trade-off in choosing mya- If mha is large, then the denominator in the bound is large. However, since mma m Mirs DKL Puis... Poisy and ( ull will also become large since smaller ma will lead to less reliable outputs.
Generalization Bounds for Noisy Iterative Algorithms
We will now exploit Theorem 5.1 and 5.2 to analyze concrete algorithms. Specifically, in noisy iterative algorithms, all the iterations are related through Markov structure, which can naturally apply the information chain rule. Our theoretical results focus on one popular instance: SGLD [19],
which is variant of Stochastic Gradient Descent (SGD) with the addition of a scaled isotropic Gaussian noise to each gradient step. The injected noise allows SGLD to escape the local minima and asymptotically converge to global minimum for sufficiently regular non-convex objectives [43). is worth mentioning that other types of iterative algorithms such as SG-HMC can be also analyzed within theoretical framework, which is left the future work.
Since the algorithms be analyzed require sampling mini-batches of sample at each iteration, we make the following independence assumption:
Assumption The sampling strategy is independent of the parameters and the previous samplings.
6.1 Bound for Joint Training with Bounded Gradient
In joint training, the meta and base parameters are updated simultancously. We denote & (U, Win) U W", u C R W C Rd. The training strategy is illustrated Fig la Con- cretely, the learning algorithm executes T' iterations. We further denote &' as the updated parameter at iteration E [T). with T being a random initialization.
[T] and for task E [n], we randomly sample batch B C S; of size b and an isotropic Gaussian noise ç ~ NO, ( Let e = (c....., (.), where & E U, and <! E W, Vi [n). Then the updating rule iteration can expressed as
At iteration
-' (,,(("'-1,,,, +
where G is the gradient of the empirical meta-risk on Bin,, w.r.t. all the parameters 4 and where me the learning rate. addition, we assume bounded gradients:
Assumption 2 The gradients are bounded, i.e.,
sup
|G S L, with L > 0.
de Rind+t) 2

---

Then the mutual information in Theorem 5.1 can be upper-bounded as follows.
Theorem 6.1. Based on Theorem 5.1 for the SGLD algorithm that satisfies Assumptions & 2, the mutual information for joint training sattifies
I( 11m) 2 Ei=1 nd+t log(1 +
(nd+k)o;
Specifiially, of Tt, and = for > O, we have:
joi gerfmeta (T, Anseay
S at Vam
Velloel T +c.
See the proof in Appendix B.4 It is worth mentioning that Amit and Meir M used C 2dd W C Rd They adopt similar variational form of our mutual information bound, where they use a factorized Gaussian Qe ((, I2a) to approximate Puis and Qs. = =N(pu of) to approximate Pw,uSS They set Pt: = (0, Tıaa), and Pw.ju' = (WH,, oy.), where (fr.of)) ~ Qo. Then they optimize the meta empirical risk plus the bound w.r.t. the parameters E R2d and (f) R by SGD. Our method is different since we do not use parametric approximations. Instead, we simulate the joint distribution with SGLD.
6.2 Bound for Alternate Training with Gradients Incoherence
The updating strategy for alternate training illustrated Fig. Tb We also use SGLD for the meta learner Amein and base learner Anuse and denote this algorithm by Meta-SGLD To build a connection with MAML, we consider the scenarios with 24 W C Rd, where meta meta-parameter U is a common initialization for the task parameters Wi: achieve a fast adaptation.
The Meta-SGLD algorithm has nested loop structure: the outer loop includes T iterations of SGLD for updating the meta- parameters U: at each outer loop iteration 1 E [7), there exists several parallel inner loops, where each loop is K--iteaaioon SGLD to update different task specific parameters W,.
Outer Loop Updates
It is computationally expensive to learn meta information from all the tasks when the number of
tasks is large-a common situation in few-shot learning. Thus, for each / E (T), we sample a mini- batch of tasks that are indexed by I C [n]. Then the corresponding meta-train and meta- meta-validation
data sets are denoted as By, and B respectively. The task specific parameters are denoted as Wi, {W; : E It). In addition, an isotropic Gaussian noise gt ~ NO Lal is also injected during the update. Then, the update rule w.r.t. is expressed as:
U = =-=--1-- Th Rg, (Ut- +
where RBy (U*- = | Eier Ewi~P Piging o -t [g (Wi)) is the empirical meta risk evaluated on By, and is the meta learning rate at f. addition, we denote the gradient incoherence of meta parameter U at iteration / as exe Vîn, (U--1) - VnRY (U--1).
Inner Loop Updates
Given the outer loop iteration t, for each inner iteration & [K]. randomly sample batch of data for task E I from B (the i-th task in BY,), which is denoted as B Then the update rules for the task parameters can be formulated as:
W = U+-1 W W B.A RRg Lee
(W cLk,
where 3r is the learning rate for task parameter, çt. ~ o( is the injected isotropic Gaussian noise (not shown in the figure) at inner iteration k. Analogously, we can compute the gradient incoherence w.r.t. the task parameters W We first sample a batch B from BYT B", (the union of training and validation task batches). Then the gradient incoherence of task specific parameters at the k-th inner update, task i, and outer iteration & is defined as: def CLi.K VRB,L (W -Rgg (W!-1))
Relation to MAMI Without the noise injection, the whole updating protocol described above is exactly MAML. Specifically, if we set K 1, the empirical meta loss be expressed as:
7

---

RBY (U--1) = 1 Eiel, RE (W?) = 1 Eiel, Rey, (0-- Br,1 V VRm (U*-1),, and [Td
[7.1
Iill EiEl, V. (W is the first-order MAML gradient.
Based on the nested loop structure and the independent sampling strategy, we have the following data-dependent generalization-eroo bound for Meta-SGLD.
Theorem 6.2. Based on Theorem 5.2 for the Meia-SGL.D that satisfies Assumption 1, if we set
o, = -22//// /nt Ut /2 P.P.a//Te. where and Ni are the inverse temperatures. The meta generalization error for alternate training satisfies
2x 2 Wim: Ian Iin
S
ggen al
meta (T, SGLD,
EU +E
where
T
ne 11
14 K
Ye E.
EU
E Byg By, Wi, U1-1 1=1
ew Σ
Σ
E
B B W..
2
2
The proof is provided in Appendix B.5 reflects the generalization eтror bound of the meta learner, and cw, which reflects the generalization bound of the base learner. Moreover, ey and éw are characterized by the accumulated gradient incoherence and predefined constants such as learning rates, inverse temperatures, and number of Theorem 6.2 exploits the gradient differ- ence between two batches rather than the Lipschitz constant of the loss function (and, consequently, its tighter estimation, the gradient norm of the empirical meta-risk and the individual task risks). This give more realistic generalization error bound since the Lipschitz constant for neural networks is often very large [17]. In contrast, our empirical results reveal (see Scc(7) that the gradient incoherence be much smaller than the gradient norm average. Note that have chosen fixed and large inverse temperatures to ensure small injected noise variance from the beginning of training. In addition, the step sizes also affect the bound w.r.t. training iteration numbers T, K. For example, assuming that the gradient incoherence is bounded, if we choose 1/2 = 7 Ar, = 1 meta generalization error bound is in (v log I + 22 log K), where are some constants. In contrast, when learning rates are fixed, the bound is in O(vaT +KTK).
The bound of Theorem 6.2 consists of two parts: cv. which
iterations. Compared with previous works such as [3 30
z the
7 Empirical Validations
We validate Theorem 6.2 on both synthetic and real data. The numerical results demonstrate that, in most situations, the gradient incoherence based bound is orders of magnitude tighter than the conventional meta learning bounds with the Lipschitz assumption, which is estimated with gradient norms
7.1 Synthetic Data
We consider a simple example of 2D mean estimation to illustrate the meta-learning setup. We assume that the environment is truncated 2D Gaussian distribution v((-4,-4)² 5112), A new task is also defined as a 2D Gaussian N(J,, 0. 0.11l)) with μ т. To generate few-shot tasks, we sample 20000 tasks from the environment with μ4 T, Vi [n). After sampling μ4 for each task, further sample m 16 data points from ((a, 0.112). At each iteration t, we randomly choose subset of tasks (44 = 5) from the whole data set. We evaluate on three different few-shot settings with mya {1. 8, 15) and the corresponding train size my = {15.8, 8, 1}. The detailed experiment setting is in Appendix E.
The estimated meta-genent gettaageneralzzttion upper bounds are shown in Fig. 2 For a better understanding of the generalization behaviour w.r.t. the meta learner and base learner, separately show the estimated bounds of a bound are estimated via Monte-Carlo sampling. To compare the conventional Lipschiz bound with
(Fig. 2 a)) and Eit (Fig. b)). The expectation terms within the
CCode available http:::/giituu...m////v//////att

---

ours, we approximately calculated tighter estimation of the bound with the expected gradient norm each iteration [88] instead of using fixed Lipschitz constant, which extremely vacuous in deep learning. The other components remain the same as the gradient incoherence bound.
The results on the synthetic data set reveal substantial theoretical benefit compared with the conventional Lipschitz bound. Specifically, the magnitude of the bound is improved by factor of 10 100. Interestingly, the gap between the gradient-norm and the gradient-incoherence bound is smallest when ma 15. These theoretical results reveal that the generalization bound is unavoidably large the base learner is trained on extremely few data (e.g., I-shot scenario). Since too few train data (small m.) induces high randomness and large instability in each training task.
To further validate Theorem 6.2, We calculated the actual generalization gap by evaluating the expected difference between the train loss and test loss for the above mentioned tree settings. The actual generalization gap of Mhr 1 is also much larger compared to the other two setting, which also demonstrated the instability for extreme few shot learning (See Table and 3 in Appendix
D.I
10
6_rom
167
0 mm
b+b
m, 3-3
muind
n. J-g
10"
pwit
15
1-1
m_ 1-15
Iv n [-]
n. p-15
100
150
200
spach
Training eacch
(a) Bound o U
(b) Bound of W
Figure 2: Synthetic data: Estimation of the generalization-error bound during the training (T 200). Left Estimated error bound w.r.t. meta-learner. Right The estimated error bound w.r.t. the base- learner. The curves in Blue solid line and Orange dashed line represent the estimated bound through gradient-norm (G Norm) and gradient-incoherenee (G Inco) in different few-shot settings.
7.2 Few-Shot Benchmark
To evaluate the proposed bound in modern deep few-shot learning scenarios, have tested the Meta-SGLD algorithm on the Omniglot dataset [44]. The Omniglot dataset contains 1623 characters for 50 different alphabets, and each character is present in 20 instances. We followed the experimental protocol of [45]] 2), which aims to learn a N-way classification task for 1-shot or 5-shot learning. In experiment, we conducted 5-way classification learning. A train task consists of five classes (characters) randomly chosen from the first 1200 characters, each class has m = 16 samples selected from the 20 instances. Similarly, test task contains five classes randomly sampled from the rest 423 characters. Therefore, the meta train set has
(1200) tasks. At each epoch, we have trained the model with [T| = 32 tasks. Analogous to the simulated data, we have conducted our experiment with my = {15, 8, }} and mya = {1, 8, 15) and separately visualized the two components of the bound. The detailed experimental setting is provided in Appendix E.2
The estimated bounds are shown Fig. Analogous to the results on synthetic data, the estimated error bound trough cradient-incohered 8, 15. In particular, the gradient-incohere tighter than the gradient-norm based bound when m, = bound w.r.t. U much tighter than the gradient-norm bound when my 15, which illustrates the benefits of the proposed theory. Simultaneously, the gradient-incoheren
bound similar to the gradient-norm bound when mär = 1, illustrating a theoretical limitation of learning with very few meta-train samples. Moreover, we observe that the optimal values for mmm depends on the environment since the tightest bound for Omniglot achieved with maa = 8, which is different from what we have found for the synthetic data.

---

10"
@urom
...
8_31
10"
O Guram
... 0_3o0
m.r-d
1-15
300
1003
1503
2003
500
1000
1500
2000
Train ng spoch
Tra ring spoch
(a) Bound of U
(b) Bound of W
Figure 3: Omniglot: Estimation of the generalization-erro bound during the training (T = 2000). The curves in Blue solid line and Orange dashed line represent the estimated bound through gradient-norm (G_Norm) and gradient-incoherence (G Inco)) in different few-shot settings
Finally, we observed that the component of the generalization error bound that originates from task-specific parameters is numerically larger than the one the originates from the meta parameter, has compared to the results for simulated data. This perhaps illustrates an inherent difficulty in learning few-shot tasks with high-dimensional and complex data sets, where estimating the generalization enror bound apparently more challenging. Additional experimental results for test accuracy comparison with MAML on the aforementioned tree settings are presented in Appendix D.2 Comparison and 7 We
of bound values with the observed generalization error is also included (See Table 5 believe the less evident improvement with gradient incoherence bound compared to Synthetic data can be ascribed to the utilization Batch Normalization.
Conclusion
We derived a novel information thcoretic analysis of the generalization property of meta-learning and provided Aggorith--depender generalization error bounds for both joint training and alternate training. Compared to previous gradient- baasentt-baedddde bounds that depend on the square norm of gradients, empirical validations on both simulated data and few-shot benchmark show that the proposed bound orders of magnitude tighter in most situations. Finally, we think that these theoretical results can inspire new algorithms through deeper exploration of the relation between meta peta-parameters and task paramerresssrss.
Acknowledgments and Disclosure of Funding
Work partly supported by NSERC Discovery Grant RGPIN-2016-05942 and the China Scholar- ship Council. We also thank SSQ Assurances and NSERC for their financial support through the Collaborative Research and Development Grant CRDPJ 529584 18.
References
[1] Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference on Machine Learning, pages 205-214, 2018.
[2] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In ICML,, 2017.
[3] Sebastian Thrun and Lorien Pratt. Learning to learn: Introduction and overview. Learning to learn, pages 3-17. Springer, 1998.
[4] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: 09055, 2018. 2018.
10

---

[5] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. /4165, 2020.
[6] Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. arXiv preprini 1rXiv:1711.04000 2017.
[7] Sachin Ravi and Alex Beatson. Amortized bayesian meta-learning. In International Conference on Learning Representations, 2018.
[8] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 4080-4090, 2017.
[9] Flood Sung, Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1199-108, 2018
[10] Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. In Interna- lional Conference on Learning Representations, 2016.
[11] Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-198, 2000.
[12] Anastasia Pentina and Christoph Lampert. pac-bayesian bound for lifelong learning. In International Conference on Machine Learning, pages 991-999, 2014.
[13] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-lent stochastic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566-1575. PMLR, 2019.
[14] Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning. In International Conference on Machine Learning, pages 424-433 PMLR, 2019.
[15] Aolin Xu and Maxim Raginsky. Information-theorrtiic analysis of generalization capability of learning algorithms. Advances Neural Information Processing Systems, pages 2017.
[16] Jaesik Yoon, Taesup Kim, Ousmane Dia, Sungwoong Kim, Yoshua Bengio, and Sungjin Ahn. Bayesian model-agnostic meta-learning. In Advances in Neural Information Processing Systems, pages 7332-7342, 2018.
[17] Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 3839-3848, 2018.
[18] Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. arXiv preprint arXiv: 2019.
[19] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-I pages 681-688, 2011.
[20] Sharu Theresa Jose and Osvaldo Simeone. Information-thheoreicc generalization bounds for meta-lcarning and applications. arXiv preprint arXiv:2005.0433 2020.
[21] Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv preprint arXiv: /909, /2488, 2019.
[22] Hao Liu, Richard Socher, and Caiming Xiong. Taming maml: Efficient unbiased meta- reinforcement learning. In International Conference on Machine Learning, pages 4061-4071. PMLR, 2019.

---

[23] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. arXiv preprint arXiv:2002.07948, 2020.
[24] Liang-Yan Gui, Yu-Xiong Wang, Deva Ramanan, and José MF Moura. Few-shot human motion prediction via meta-learning In Proceedings of the European Conference Computer Vision (ECCV), pages 432 4500, 2018.
[25] Alex Nichol and John Schulman. Reptile: a scalable metalearning algorithm. arXiv preprint arXiv:1803.02999 2(3):4, 2018.
[26] Chelsea Finn, Kelvin Xu, and Sergey Levine. Probabilistic model-agnostic meta-learning, In Advances in Neural Information Processing Systems, pages 9516-9527, 2018.
[27] Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas Griffiths. Recasting gradient-based meta-learning as hierarchical bayes. International Conference on Learning Representations, 2018.
[28] Mikhail Khodak, Maria-Florima Balcan, and Ameet Talwalkar. Adaptive gradient-base -baed meta- learning methods. arXiv preprint orXiv:1906.02711 2019.
[29] Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-within-onlig meta-learning. In ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019), volume 32, pages 1-11. Neural Information Processing Systems (NeurIPS 2019). 2019.
[30] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning In International Conference on Machine Learning, pages 1920-1930. PMLR, 2019.
[31] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar.
On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In International Conference on Artificial Intelligence and Statisties, pages 1082 1092. PMLR, 2020.
[32] Kaiyi Ji, Junjie Yang, and Yinghin Liang. Multi-step model-agnostic meta-learning: Conver- gence and improved algorithms. arXiv preprint arXiv:2002.0785 07836, 2020.
[33] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around common mean. In ADVANCES IN NEURAL. INFORMATION PROCESSING SYSTEMS 3/ (NIPS 2018), volume 3.. NIPS Proceedings, 2018.
[34] Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lee, Sham Kakade, Huan Wang, and Caiming Xiong. How important the train-validation split in meta-lcarning? In International Conference Machine Learning, pages 543-553, PMLR, 2021.
[35] Nikunj Saunshi, Arushi Gupta, and Wei Hu. A representation learning perspective the importance of train-validation splitting in meta-learning. In International Conference on Machine Learning, pages 9333-9343. PMLR, 2021.
[36] Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-322 2019.
[37] Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information-basee bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, 2020.
[38] Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018
[39] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. information-theoree generalization bounds for sgid via data-dependent estimates. In Advances Neural Information Processing Systems, pages 11015-11025, 2019.
[40] Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. arXiv preprint arXiv:2001.09122, 2020.
12

---

[41] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredee The benefit of multitask representation learning. The Journal of Machine Learning Research, (7(1):2553-2886 2016.
[42] David McAllester and Karl Stratos. Formal limitations on the measurement mutual infor- mation. In International Conference on Artificial Intelligence and Statistics, pages 875-884. PMLR, 2020.
[43] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
[44] Brenden Lake, Ruslan Salakhutdinov, Jason Gross, and Joshua Tenenbaum. One shot learning of simple visual concepts. Proceedings of the annual meeting of the cognitive science society, volume 33, 2011.
[45] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. arXiv preprint arXiv: 006004080 2016.
[46] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymptotic theory of independence. Oxford university press, 2013.
[47] Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. Pac-bayesian theory meets bayesian inference. In Advances in Neurul Information Processing Systems, pages 1884-1892, 2016.
[48]
Liangqu Long. Maml-pytorch implementation. MAML Pytorch 2018.
https://gthhub..oo//rrgg11111
[49]
Ron
Amit. meta-leamiing-ddjusinng priios
https://github.comm/omm
meta Leta-learning-aae aasaamminnnadiusstin---iiroo-e 2019.
13


Reviews:
[{"review_id": "xOsahsTIj-d", "reviewer": "Reviewer_YsVe", "summary": "This paper extends recent information-theoretic approaches for computing model generalization to the meta-learning setting. They prove algorithm/data-dependent bounds for both the joint-training and support-query meta-learning strategies and instantiate the results for variants of gradient-based meta-learning with noise injection. Finally, they compute generalization bounds on synthetic and Omniglot data.", "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": "Following the author response I have increased my score under the assumption that the additional discussions of closely related work and the new empirical generalization error results appear in the revised version.\n\n# Original review\n\nThe extension of single-task information-theoretic generalization bounds to the meta-learning setting, together with the use of gradient incoherence-based bounds, seems like a meaningful and useful theoretical contribution. I lean towards acceptance of the paper, although I do believe there is not a significant amount of practical insight provided and the some experimental results and comparisons are missing, as discussed below; I think including them would significantly improve the paper.\n\n### Strengths:\n1. The paper proves new information-theoretic meta-learning generalization bounds. The bounds are algorithm/data-dependent and, when instantiated for MAML-like algorithms, rely on gradient incoherence rather than the gradient norm, allowing them to yield non-vacuous results. \n2. Results are provided for both the joint training and support-query settings, which is an important direction for understanding meta-learning.\n3. Experimental results demonstrate the usefulness of the bounds.\n4. Code is released.\n\n### Weaknesses:\n1. I believe the paper would be significantly improved with more discussion comparing the results here directly to past work on meta-learning and information-theoretic generalization bounds. For the former, as discussed in the comments there are several recent papers that explicitly discuss the support-query approach and make direct comparisons to joint training. I believe there are useful comparisons to be made with the results in this paper. For the latter, while there is a comparison to single-task results, it is unclear how related the theory is. Are the proofs related or different from standard results and instantiations in this setting? I am not an expert there and so it is difficult to discern.\n2. Experimentally, I believe it would be useful to compare the computed bounds with observed generalization error. This should certainly be doable for synthetic data and likely also for Omniglot. I believe this is important to give an understanding of how far away we are theoretically from practical performance.\n\n### Comments:\n17: This is not true of all few-shot learning algorithms, e.g. Reptile.  \n19: Papers by Denevi et al. (2019), Bai et al. (2021), and Saunshi et al. (2021) do discuss this in-depth.  \n102: The notation for a hypothesis w is lower-case on this line but upper-case in the inequality below. This inconsistency also appears elsewhere.  \n167: This reinforces the result of Bai et al. (2021), who showed that joint training is not asymptotically unbiased in the agnostic setting.    \n328: Doesn’t this make the meta-test distribution different from the meta-train distribution?\n\n### References:\nBai, Chen, Zhou, Zhao, Lee, Kakade, Wang, Xiong. _How important is the train-validation split in meta-learning?_ ICML 2021.  \nDenevi, Ciliberto, Stamos, Pontil. _Learning to learn around a common mean._ NeurIPS 2019.  \nSaunshi, Gupta, Hu. _A representation learning perspective on the importance of train-validation splitting in meta-learning._ ICML 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "dj2zDru7oc", "reviewer": "Reviewer_kKnc", "summary": "This paper provides information theoretic generalization bounds for meta-learning that 1) are algorithm and data dependent 2) don't depend on the norm of the gradients, but their sensitivity to the training data. This leads to stronger bounds than previous literature. Experiments on simulated data and Omniglot with the SGLD optimization algorithm confirm the theory.", "questions": "", "limitations": "", "rating": 7, "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": "# Originality and significance #\n\nThis paper is primarily of theoretical interest to other researchers. It appears to be the second to provide information-theoretic data-dependent generalization bounds for meta-learning, after Jose and Simeone (2020). The bounds provided here appear to be tighter, as they are conditional on the meta-information $U$ for joint training and the support sets for alternate training. I cannot speak to the novelty of the mathematical tools used, as I do not work in this area.\n\n# Quality #\n\nAlthough I did not check the proofs in detail, the results appear to be sound. The experimental results validate the claim that their bounds are superior to those that rely on the norm of the gradient. However, I think in order to support other claims made in the paper, it would be helpful to 1) compare the bounds to the generalization error estimated using test data and 2) compare the bounds empirically to those of Jose and Simeone (2020).\n\n# Clarity #\n\nI found the paper to be well-written and clear. I would recommend that the authors move the legends of figures 2 and 3 below - the text is somewhat difficult to read.\n\n# Update after reading response and other reviews #\n\nI have decided to raise my score from 6 to 7, as the new empirical results addressed my concerns, with the understanding that they will be included in the final draft.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "# Limitations #\n\nThe authors state that their work is limited to randomized algorithms.\n\n# Societal impact #\n\nI agree with the authors that there is no potential negative impact of the work, since it is primarily theoretical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "LGEnbJFoNyf", "reviewer": "Reviewer_zirw", "summary": "The paper extends information-theoretic bounds (Xu and Raginsky [15]) to provide generalization bounds for two meta-learning settings: Joint Training (classical setting of Baxter) and Alternate Training (that includes the MAML algorithm). The general bounds are based on the mutual information between the learning algorithm output and input. The bound is given a more explicit form for the case of a meta-SGLD algorithm, that can be described as a stochastic variant of the popular MAML algorithm. Experimental results show bounds that are orders of magnitudes smaller than norm-based bounds.", "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": " Strengths:\n\n- The results of Theorem 5.1, 5.2, and 6.2  seem very interesting, as they provide a new viewpoint to analyze the generalization properties of meta-learning algorithms.\nIn particular, Thm 5.2 sheds light on meta-learning settings with dataset split and shows a trade-off in choosing the split sizes.\n- The Meta-SGLD algorithm and its generalization guarantees seem significant since it depends on the gradient differences rather than on the Lipschitz constant of the loss (as in previous work), which can be very large in deep learning settings. \n****************************\nWeaknesses:\n\n- The main paper is well-written and easy to follow. However, the proofs are harder to follow (especially for Thm 5.1 and 5.2).  \nI suggest starting the proofs with a high-level explanation and giving motivation to each step.\n\n- The bounds in the experiments are not compared to the actual generalization gap. The figures show a generalization gap as small as 0.1. I think it is important to validate that the actual generalization gap is smaller than that.\n\n- The clarity of the experiment should be improved.  The figures lack axes annotations. I couldn’t see a description of what is plotted. What exactly is the G_Norm bound? How is it evaluated?\n\nComments:\n- Thm 6.1 and 6.2 show a trade-off in choosing $T$. It would be interesting to discuss and investigate it more.\n\n****************************\n\nMinor comments:\n- Thm 5.2: $I^{S^{tr}}$ is undefined (only defined in the appendix)\n\n\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": "IQgjYiHFTE", "reviewer": "Reviewer_v93c", "summary": "The authors derive two bounds on the generalization property of meta-learning algorithms using an information-theoretic analysis. The first one considers algorithms based on a *joint-training*, i.e.  when all the data from the tasks is used to update the parameters. The second bound is specific to algorithms learned through an *alternate training*, i.e. the tasks data are split into training and validation, training part is used to update the task-specific parameters and the validation part is used to update the meta-parameters.\nThen, they analyze two concrete algorithms based on SGLD, a joint-training version and an alternate training version, to derive the bounds for these specific cases.\nFinally, they empirically estimate the values of their bounds and compare with an empirical estimate of a previous bound based on the lipschitz constant of the network. The empirical estimation is done on synthetic data and the omniglot dataset.", "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:**__  The authors specifically studied the generalization of meta-learning algorithms through the lens of information theory. They obtained bounds depending on the mutual information between the data and the outputs of the meta-learner and the base learner, similar to what was obtained in the general case of any randomized algorithm (Xu and Raginsky [15]). The authors discuss their results and compare them with other previously obtained bounds. However, I think that the authors could emphasize more the differences in their approach that allowed them to obtain different results. The only explanation of the specificity of their approach is detailed in the proof of theorem 5.1 in the supplementary material. If I understand correctly, they do not separate the environment error and the task error, which allows them to have a tighter bound. \n\n__**Quality:**__  The approach used by the authors seems correct, and the bounds obtained are tighter than previous results. The authors provide in the experimental section an *estimation of the values* obtained in their bounds in practice and compare them with an *estimate of the values* used in previous results. The authors have thus shown that, empirically, the values of the quantities involved in their generalization bounds are smaller than those of previous results that use the Lipschitz norm of the model. This is not an empirical validation of the theory, which would show that the bounds fit with the experiments.\n\n__**Clarity:**__  The paper is very well written and well-structured, easy to read and follow. The results obtained are well detailed and compared w.r.t previous work. The explanations of the differences between the analysis done by the authors and previous analyses could be improved (as explained above). \n\n__**Significance:**__ The bounds obtained seem empirically tighter than previous bounds. It remains to be shown that they actually fit with the experiment. As mentioned by the authors, the analysis carried out here could inspire new methods, but it is not the object of the paper.\n\n## Minor Remarks\n\n- The meaning of the independent symbol between two sets should be explicitly defined (l.146).\n- I think Fig.1 should be moved higher in the paper. It is mentioned on page 4 and doesn't appear until page 6. One must scroll down to see the figure the first time it is mentioned. \n- Some minor typos I noticed:\n  - l.59 \"different ~~the~~ *from* those\"\n  - l.81 \"~~the~~ the\"\n  - l.94 \"~~of~~ of\" \n  - l.342 \"*~~h~~as* compared to\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work presented here is very theoretical. To study the possible negative impacts of this kind of work is to study the negative impacts of the whole field. On the other hand, contrary to what the authors say, meta-learning could also be used for harmful applications such as quick racial profiling of a user.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I spent between 8 to 10 hours to review this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this paper is a solid work that contributes substantially to the theory of Meta-Learning. After the rebuttal, most reviewers found the response by the authors satisfactory and raised their score. As the AC of the paper, I also read the paper and found it novel and very well-written. I recommend acceptance of this work. 


Decision: Accept (Spotlight)