Generalization Bounds for Meta-Learning: An Information-Theoretic Analysis
Year: 2022

Abstract:
We derive a novel information-theoretic analysis of the generalization property of meta-learning algorithms. Concretely, our analysis proposes a generic understanding of both the conventional learning-to-learn framework [1] and the modern model-agnostic meta learning (MAML) algorithms [2]. Moreover, we provide a data-dependent generalization bound for a 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.

heading: 1 Introduction
text: Learning a task with limited samples is crucial for real-world machine learning applications, where proper prior knowledge is a key component for a successful transfer. Meta-Learning [3] or learningto-learn (LTL) aims to extract such information through previous training tasks, which has recently re-emerged as an important topic.
Modern approaches based on MAML [2] have gained tremendous success by exploiting the capabilities of deep neural networks [4–9]. However, many theoretical questions still remain elusive. For instance, in the most popular methods for few-shot learning [10], the task-specific parameters and meta-parameter are updated in support (also called meta-train) and query (also called meta-validation) set, respectively. However, the majority of existing theoretical results such as [1, 11–14] do not provide a formal understanding of such popular practice. Moreover, modern meta-learning approaches have incorporated over-parameterized deep neural networks, where conducting the theoretical analysis becomes even more challenging.
In this paper, we introduce a novel theoretical understanding of the generalization property of metalearning through an information-theoretical 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 [11], where the meta-parameters and task-specific parameters are updated within the same data set (referred as joint training). 2) The modern MAML-based approaches where the meta-parameters and task specific parameters are updated on distinct data sets (referred as alternate training), and for which the existing theoretical analysis is rare.
Flexible Bounds The proposed meta-generalization error bounds are highly flexible: they are algorithm-dependant, data-dependant, and are valid for non-convex loss functions. 1) Specifically, the generalization error bound for joint-training (Theorem 5.1) is controlled by the mutual information ∗Department of Computer Science and Software Engineering, <qi.chen.1@ulaval.ca> †Department of Electrical Engineering and Computer Engineering, <changjian.shui.1@ulaval.ca> ‡Department of Computer Science and Software Engineering, <mario.marchand@ift.ulaval.ca>
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
between the output of the randomized algorithm and the whole data set. It can cover the typical results of [12, 1], which can be interpreted with an environment-level and a 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-validation 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 meta-generalization error bound will be small. This theoretical result is coherent with the recently-proposed Chaser loss in Bayes MAML [16].
Non-vacuous bounds for gradient-based few-shot learning Conventional gradient-based metalearning theories heavily rely on the assumption of a 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 gradient-incoherence 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) [19]. 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.

heading: 2 Related Work
text: 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 [1] 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-theoretic 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, a more detailed discussion is provided in Appendix F.
Gradient based meta-learning In recent years, gradient-based meta-learning such as MAML [2] have drawn increasing attention since they are model-agnostic and are easily deployed for complex tasks like reinforcement learning, computer vision, and federate learning [21–24]. 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 MAML[16], they propose a fast Bayesian adaption method using Stein variational gradient descent and conceived a Chaser loss which coincides with the proposed Theorem 5.2.
On the theoretical side, Denevi et al. [13] analyzed the average excess risk for Stochastic Gradient Descent (SGD) with Convex and Lipschitz loss. Balcan et al. [14] studied meta-learning 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-environment changes dynamically or the tasks share a certain geometric structure. Other guarantees for online meta-learning scenarios are provided by Denevi et al. [29] and Finn et al. [30]. Finally, [31, 32] also provided a convergence analysis for MAML-based methods.
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 et 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 a 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. Moreover, Saunshi et al. [35] analyzed the train-validation
split for linear representation learning. They showed that the train-validation split encourages learning a low-rank representation. More detailed discussion and comparison can be found in Appendix F.
Information-theoretic learning for single tasks We use here an information-theoretic approach, introduced by Russo and Zou [36] and Xu and Raginsky [15], for characterizing single-task learning. Characterizing the generalization error of a learning algorithm in terms of the mutual information between 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-information framework to a broad class of iterative algorithms, including SGLD and stochastic gradient Hamiltonian Monte Carlo (SGHMC). Negrea et al. [39] provided data-dependent estimates of information-theoretic bounds for SGLD. For a recent comprehensive study, see Steinke and Zakynthinou [40].

heading: 3 Preliminaries
text: Basic Notations We use upper case letters, e.g. X,Y , to denote random variables and corresponding 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 , PY |X denotes the conditional distribution or the Markov transition kernel. X ⊥⊥ Y means X and Y are independent. And let us recall some basic definitions: Definition 3.1. Let ψX(λ) def = logE[eλ(X−E[X])] denote the cumulant generating function(CGF) of random variable X . Then X is said to be σ-subgaussian if we have
ψX(λ) ≤ λ2σ2
2 ,∀λ ∈ R .
Definition 3.2. LetX , Y andZ be arbitrary random variables, and letDKL denote the KL divergence. The mutual information between X and Y is defined as:
I(X;Y ) def = DKL(PX,Y ||PXPY ) .
The disintegrated mutual information between X and Y given Z is defined as:
IZ(X;Y ) def = DKL(PX,Y |Z ||PX|ZPY |Z) .
The corresponding conditional mutual information is defined as:
I(X;Y |Z) def= EZ [IZ(X;Y )] .
Information theoretic bound for single task learning We consider an unknown distribution µ on an instance space Z = X × Y , and a set of independent samples S = {Zi}mi=1 drawn from µ: Zi ∼ µ and S ∼ µm. Given a parametrized hypothesis spaceW and a loss function ` :W×Z → R, the true risk and the empirical risk of w ∈ W are respectively defined as Rµ(w) def = EZ∼µ`(w,Z) and RS(w) def = (1/m) ∑m i=1 `(w,Zi).
Following the setting of information-theoretic learning [36, 15, 37], a learning algorithm A is a randomized mapping that takes a dataset S as input and outputs a hypothesis W according to a conditional distribution PW |S , i.e., W = A(S) ∼ PW |S .4 The (mean) generalization error gen(µ,A) def= EW,S [Rµ(W )−RS(W )] of an algorithm A is then bounded according to: Theorem 3.1. (Xu and Raginsky [15]) Suppose that for each w ∈ W , the prediction loss `(w,Z) is σ-subgaussian with respect to Z ∼ µ. Then for any randomized learner A characterized by PW |S , for S ∼ µm, we have
|gen(µ,A)| ≤ √ 2σ2
m I(W ;S) .
I(W ;S) is 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.
4Note that the conditional distribution PW |S is different from the posterior distribution in Bayes learning.

heading: 4 Problem Setup
text: Following [11], we assume that all tasks originate from a common environment τ , which is a probability measure on the set of probability measures on Z = X ×Y . The draw of µ ∼ τ represents encountering a learning task µ in the environment τ . To run a learning algorithm for a task, we need to draw a set of data samples from µ. In meta learning, there are multiple tasks, for simplicity, we assume that each task has the same sample size m. Based on Maurer et al. [41], the environment τ induces a mixture distribution µm,τ on Zm such that µm,τ (A) = Eµ∼τ [µm(A)],∀A ⊆ Zm. Thus the m data points in S that are independently sampled from a random task µ encountered in τ is denoted as S ∼ µm,τ . Consequently, for n train tasks that are independently sampled from the environment τ , each train data set is denoted as Si ∼ µm,τ for i ∈ [n]. Analogously, for k test tasks data sets, we denote Stei ∼ µm,τ for each i ∈ [k]. We further denote the (full) training set as S1:n = (S1, ..., Sn) and the (full) testing set as Ste1:k = (S te 1 , ..., S te k ).
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 a meta parameter U ∈ U to represent this shared knowledge. We also denote by W1:n = (W1, . . . ,Wn) the task specific parameters, where each Wi ∈ W,∀i ∈ [n]. By exploring the relations between U and W , we can design different meta learning algorithms. For example, [12, 1] 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 to be an initialization of W (hence, U =W) for a gradient-descent base learner.
We define the meta learnerAmeta as an algorithm that takes the data sets S1:n as input, and then outputs a random meta-parameter U = Ameta(S1:n) ∼ PU |S1:n , which is a distribution that characterizes Ameta. When learning a new task, the base learner Abase uses a new data set S ∼ µm,τ and the estimated meta-parameter U to output a stochastic predictor W = Abase(U, S) ∼ PW |U,S .5
To evaluate the quality of the meta information U for learning a new task, we define the true meta risk, given the base learner Abase, as
Rτ (U) def = ES∼µm,τEW∼PW |S,U [Rµ(W )] .
Joint Training & Alternate Training
Since τ and µ are unknown, we can only estimate U and W from the observed data. Generally, there are two different types of methods for evaluating meta and task parameters.
5Although the base learner is the same, PWi|U,Si is different for each task i due to the different data set Si.
For Joint Training [1, 12], the whole dataset S1:n is used to jointly evaluate all the parameters (U,W1:n) in parallel. A similar training protocol is illustrated in Fig. 1a. Then the corresponding empirical meta risk w.r.t. U is defined as:
RS1:n(U) def = 1n ∑n i=1 EWi∼PWi|Si,U [RSi(Wi)].
For Alternate training, used in modern deep meta-learning algorithms [2], Si is randomly split into two smaller datasets: a meta-train set Stri with |Stri | = mtr and a meta-validation set Svai with |Svai | = mva examples for each i ∈ [n]. In few-shot learning, Str1:n and Sva1:n are denoted as the support set and query set. Additionally, we have m = mtr +mva and Stri ⊥⊥ Svai . An example of the training protocol is illustrated in Fig. 1b, where (U,W1:n) are alternately updated through Sva1:n and S tr 1:n, respectively. The corresponding empirical meta risk w.r.t U is defined as:
R̃S1:n(U) def = 1n ∑n i=1 EWi∼PWi|Stri ,U [RS va i (Wi)]
Then, the meta generalization error within these two modes w.r.t. Ameta and Abase are respectively defined as
genjoimeta(τ,Ameta,Abase) def = EU,S1:n [Rτ (U)−RS1:n(U)],
genaltmeta(τ,Ameta,Abase) def = EU,S1:n [Rτ (U)− R̃S1:n(U)] .

heading: 5 Information-Theoretic Generalization Bounds
text: 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 theoretical results are valid for any randomized algorithm Ameta and Abase. But for some deterministic algorithms producing deterministic predictors, the mutual information bound can be vacuous.

heading: 5.1 Mutual Information (MI) Bound in Joint Training
text: Theorem 5.1. Suppose all tasks use the same loss `(Z,w), which is σ-subgaussian for each w ∈ W , where Z ∼ µ, µ ∼ τ . Then, the meta generalization error for joint training is upper bounded by
|genjoimeta(τ,Ameta,Abase)| ≤ √ 2σ2
nm I(U,W1:n;S1:n) .
The proof of Theorem 5.1 is presented in Appendix B.1. Moreover, according to the chain rule of mutual-information, the error bound in Theorem 5.1 can be further decomposed as√
2σ2 mn (I(U ;S1:n) + ∑n i=1 I(Wi;Si|U)) ≤ √ 2σ2 mn I(U ;S1:n) + √ 2σ2 mn ∑n i=1 I(Wi;Si|U) .
Discussions The first and second terms reflect, respectively, the environmental and task-level uncertainty. 1) In the limit of a very large number of tasks (n→∞) 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 a bias in general. However, this non-zero term will be smaller than the mutual information of single-task learning. Indeed, let I(W ;S) denotes the mutual information of single-task learning, we have, as shown in Appendix B.2, that I(W ;S) ≥ I(W ;S|U) ≈ 1n ∑n i=1 I(Wi;Si|U), which illustrates the benefits of learning the meta-parameter U . 2) When we have a constant number n of 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-information assists a new task to learn. If the new task has a sufficiently large number m of samples, the generalization error will be small, and the meta-information U does not significantly help learning the new task.
Relation with previous work Since mutual information implicitly depends on the unknown distribution τ , it is hard to estimate and minimize [42]. By introducing an arbitrary distribution-free prior Q on U ×Wn, we can upper bound I(U,W1:n;S1:n) ≤ I(U,W1:n;S1:n) + DKL(PU,W1:n ||Q) = ES1:nDKL(PU,W1:n|S1:n ||Q) (see Lemma A.1). If we set a joint prior Q = P × ∏n i=1 P , then the bound of Theorem 5.1 becomes similar to the one proposed by [1], where P is the hyper-prior and P is the task-prior in their settings. Finally, note that the bound of Theorem 5.1 is tighter than the one proposed by [12], where the KL divergence is outside of the square root function.

heading: 5.2 Conditional Mutual Information (CMI) Bound for Alternate Training
text: Theorem 5.2. Assume that all the tasks use the same loss function `(Z,w), which is σ-subgaussian for each w ∈ W , where Z ∼ µ, µ ∼ τ .Then we have
|genaltmeta(τ,Ameta,Abase)| ≤ EStr1:n
√ 2σ2IS tr 1:n(U,W1:n;S va 1:n)
nmva ≤
√ 2σ2I(U,W1:n;Sva1:n|Str1:n)
nmva .
See the proof in Appendix B.3. The second inequality is obtained with the Jensen’s inequality for the concave square root function and Lemma A.3. Additionally, we can apply the chain rule on the conditional mutual information, to obtain the following decomposition:
I(U,W1:n;S va 1:n|Str1:n) = I(U ;Sva1:n|Str1:n) + ∑n i=1 I(Wi;S va i |U, Stri )
= ES1:nDKL(PU |S1:n ||PU |Str1:n) + EU,S1:n ∑n i=1DKL(PWi|Si,U ||PWi|Stri ,U )).
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 meta-generalization error bound will be small. Moreover, since the bound of Theorem 5.2 is data-dependent w.r.t. Str1:n, 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 mva. If mva is large, then the denominator in the bound is large. However, since mva = m −mtr, DKL(PU |S1:n ||PU |Str1:n) and DKL(PWi|Si,U ||PWi|Stri ,U ) will also become large since smaller mtr will lead to less reliable outputs.

heading: 6 Generalization Bounds for Noisy Iterative Algorithms
text: 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 a Markov structure, which can naturally apply the information chain rule. Our theoretical results focus on one popular instance: SGLD [19], which is a 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]. It is worth mentioning that other types of iterative algorithms such as SG-HMC can be also analyzed within our theoretical framework, which is left as the future work.
Since the algorithms to be analyzed require sampling mini-batches of sample at each iteration, we make the following independence assumption:
Assumption 1 The sampling strategy is independent of the parameters and the previous samplings.

heading: 6.1 Bound for Joint Training with Bounded Gradient
text: In joint training, the meta and base parameters are updated simultaneously. We denote Φ def= (U,W1:n) ∈ U × Wn, U ⊆ Rk,W ⊆ Rd. The training strategy is illustrated in Fig 1a. Concretely, the learning algorithm executes T iterations. We further denote Φt as the updated parameter at iteration t ∈ [T ], with Φ0 being a random initialization. At iteration t ∈ [T ] and for task i ∈ [n], we randomly sample a batch Bti ⊆ Si of size b and an isotropic Gaussian noise ξt ∼ N(0, σ2t I(nd+k)). Let ξt = (ξt0, . . . , ξtn), where ξt0 ∈ U , and ξti ∈ W, ∀i ∈ [n]. Then the updating rule at iteration t can be expressed as
Φt = Φt−1 − ηtG(Φt−1, Bt1:n) + ξt , where G is the gradient of the empirical meta-risk on Bt1:n w.r.t. all the parameters Φ, and where ηt is the learning rate. In addition, we assume bounded gradients:
Assumption 2 The gradients are bounded, i.e., sup Φ∈R(nd+k),s∈Zbn ||G(Φ, s)||2 ≤ L, with L > 0.
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 1 & 2, the mutual information for joint training satisfies
I(Φ;S1:n) ≤ ∑T t=1 nd+k 2 log(1 + η2tL 2
(nd+k)σ2t ) .
Specifically, if σt = √ ηt, and ηt = ct for c > 0, we have:
|genjoimeta(τ,Ameta,Abase)| ≤ σL√nm √ c log T + c .
See the proof in Appendix B.4. It is worth mentioning that Amit and Meir [1] used U ⊆ R2d,W ⊆ Rd. They adopt a similar variational form of our mutual information bound, where they use a factorized Gaussian Qθ = N (θ, I2d) to approximate PU |S1:n and Qφi = N (µi, σ2i ) to approximate PWi|U,Si . They set PU = N (0, I2d), and PWi|U = N (µP , σ2P ), where (µP , σ2P ) ∼ Qθ. Then they optimize the meta empirical risk plus the bound w.r.t. the parameters θ ∈ R2d and (µi, σ2i ) ∈ R2d by SGD. Our method is different since we do not use parametric approximations. Instead, we simulate the joint distribution with SGLD.

heading: 6.2 Bound for Alternate Training with Gradients Incoherence
text: The updating strategy for alternate training is illustrated in Fig. 1b. We also use SGLD for the meta learnerAmeta and base learnerAbase, and denote this algorithm by Meta-SGLD. To build a connection with MAML, we consider the scenarios with U =W ⊆ Rd, where meta-parameter U is a common initialization for the task parameters W1:n to achieve a fast adaptation.
The Meta-SGLD algorithm has a nested loop structure: the outer loop includes T iterations of SGLD for updating the meta-parameters U ; at each outer loop iteration t ∈ [T ], there exists several parallel inner loops, where each loop is a K-iteration SGLD to update different task-specific parameters Wi.
Outer Loop Updates
It is computationally expensive to learn meta information from all the tasks when the number n of tasks is large—a common situation in few-shot learning. Thus, for each t ∈ [T ], we sample a minibatch of tasks that are indexed by It ⊆ [n]. Then the corresponding meta-train and meta-validation data sets are denoted as BtrIt and B va It
, respectively. The task specific parameters are denoted as WIt = {Wi : i ∈ It}. In addition, an isotropic Gaussian noise ξt ∼ N (0, σ2t Id) is also injected during the update. Then, the update rule w.r.t. U is expressed as:
U t = U t−1 − ηt∇R̃BvaIt (U t−1) + ξt ,
where R̃BvaIt (U t−1) = 1|It| ∑ i∈It EWi∼PWi|Btri,t,Ut−1 [RB va i,t (Wi)] is the empirical meta risk evaluated on BvaIt , and ηt is the meta learning rate at t. In addition, we denote the gradient incoherence of meta parameter U at iteration t as ut def = ∇R̃BIt (U t−1)−∇R̃BtrIt (U t−1).
Inner Loop Updates
Given the outer loop iteration t, for each inner iteration k ∈ [K], we randomly sample a batch of data for task i ∈ It from Btri,t (the i-th task in BtrIt), which is denoted as B tr i,t,k. Then the update rules for the task parameters can be formulated as:
W 0i,t = U t−1 ,W ki,t = W k−1 i,t − βt,k∇RBtri,t,k(W k−1 i,t ) + ζ t,k ,
where βt,k is the learning rate for task parameter, ζt,k ∼ N (0, σ2t,kId) 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 ki,t. We first sample a batch Bi,t,k from Bvai,t ⋃ Btri,t (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 t is defined as: wt,i,k def = ∇RBi,t,k(W k−1 i,t )−∇RBtri,t,k(W k−1 i,t ).
Relation to MAML Without the noise injection, the whole updating protocol described above is exactly MAML. Specifically, if we set K = 1, the empirical meta loss can be expressed as:
R̃BvaIt (U t−1) = 1|It| ∑ i∈It RBvai,t(W K i,t) = 1 |It| ∑ i∈It RBvai,t(U t−1 − βt,1∇RBtri,t,1(U t−1)) , and
1 |It| ∑ i∈It ∇RBvai,t(W K i,t) is the first-order MAML gradient.
Based on the nested loop structure and the independent sampling strategy, we have the following data-dependent generalization-error bound for Meta-SGLD.
Theorem 6.2. Based on Theorem 5.2, for the Meta-SGLD that satisfies Assumption 1, if we set σt = √ 2ηt/γt, σt,k = √ 2βt,k/γt,k, where γt and γt,k are the inverse temperatures. The meta generalization error for alternate training satisfies
|genaltmeta(τ, SGLD, SGLD)| ≤
√ 2σ2I(U,W1:n;Sva1:n|Str1:n)
nmva ≤ σ√ nmva √ U + W ,
where
U = T∑ t=1 EBvaIt ,BtrIt ,WIt ,Ut−1 ηtγt‖ ut ‖22 2 , W = T∑ t=1 |It|∑ i=1 K∑ k=1 EBvai,t,k,Btri,t,k,Wk−1i,t βt,kγt,k‖ wt,i,k‖22 2 .
The proof is provided in Appendix B.5. The bound of Theorem 6.2 consists of two parts: U , which reflects the generalization error bound of the meta learner, and W , which reflects the generalization bound of the base learner. Moreover, U and W are characterized by the accumulated gradient incoherence and predefined constants such as learning rates, inverse temperatures, and number of iterations. Compared with previous works such as [13, 30], Theorem 6.2 exploits the gradient difference 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 can give a more realistic generalization error bound since the Lipschitz constant for neural networks is often very large [17]. In contrast, our empirical results reveal (see Sec 7) that the gradient incoherence can be much smaller than the gradient norm on average. Note that we 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 ηt = 1t , βt,k = 1 tk , the
meta generalization error bound is in O( √ c1 log T + c2 logK), where c1, c2 are some constants. In
contrast, when learning rates are fixed, the bound is in O( √ c1T + c2TK).

heading: 7 Empirical Validations
text: 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.6

heading: 7.1 Synthetic Data
text: We consider a simple example of 2D mean estimation to illustrate the meta-learning setup. We assume that the environment τ is a truncated 2D Gaussian distribution N ((−4,−4)T , 5I2). A new task is also defined as a 2D GaussianN (µ, 0.1I2) with µ ∼ τ . To generate few-shot tasks, we sample n = 20000 tasks from the environment with µi ∼ τ,∀i ∈ [n]. After sampling µi for each task, we further sample m = 16 data points from N (µi, 0.1I2). At each iteration t, we randomly choose a subset of 5 tasks (|It| = 5) from the whole data set. We evaluate on three different few-shot settings with mva = {1, 8, 15} and the corresponding train size mtr = {15, 8, 1}. The detailed experiment setting is in Appendix E.1.
The estimated meta-generalization upper bounds are shown in Fig. 2. For a better understanding of the generalization behaviour w.r.t. the meta learner and base learner, we separately show the estimated bounds of σ √ U nmva (Fig. 2(a)) and σ √ W nmva
(Fig. 2(b)). The expectation terms within the bound are estimated via Monte-Carlo sampling. To compare the conventional Lipschiz bound with
6Code is available at: https://github.com/livreQ/meta-sgld.
ours, we approximately calculated a tighter estimation of the bound with the expected gradient norm at each iteration [18] instead of using a fixed Lipschitz constant, which is extremely vacuous in deep learning. The other components remain the same as the gradient incoherence bound.
The results on the synthetic data set reveal a substantial theoretical benefit compared with the conventional Lipschitz bound. Specifically, the magnitude of the bound is improved by a factor of 10 to 100. Interestingly, the gap between the gradient-norm and the gradient-incoherence bound is smallest when mva = 15. These theoretical results reveal that the generalization bound is unavoidably large if the base learner is trained on extremely few data (e.g., a 1-shot scenario). Since too few train data (small mtr) 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 mtr = 1 is also much larger compared to the other two setting, which also demonstrated the instability for extreme few shot learning (See Table 1, 2 and 3 in Appendix D.1).

heading: 7.2 Few-Shot Benchmark
text: To evaluate the proposed bound in modern deep few-shot learning scenarios, we 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 our experiment, we conducted a 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, a test task contains five classes randomly sampled from the rest 423 characters. Therefore, the meta train set has n = ( 1200
5
) tasks. At each epoch, we have trained the
model with |It| = 32 tasks. Analogous to the simulated data, we have conducted our experiment with mtr = {15, 8, 1} and mva = {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 in Fig. 3. Analogous to the results on synthetic data, the estimated error bound trough gradient-incoherence is tighter than the gradient-norm based bound when mtr = 8, 15. In particular, the gradient-incoherence bound w.r.t. U is much tighter than the gradient-norm bound when mtr = 15, which illustrates the benefits of the proposed theory. Simultaneously, the gradient-incoherence bound is similar to the gradient-norm bound when mtr = 1, illustrating a theoretical limitation of learning with very few meta-train samples. Moreover, we observe that the optimal values for mva depends on the environment since the tightest bound for Omniglot is achieved with mva = 8, which is different from what we have found for the synthetic data.
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 error bound is apparently more challenging. Additional experimental results for test accuracy comparison with MAML on the aforementioned tree settings are presented in Appendix D.2 Table 4. Comparison of bound values with the observed generalization error is also included (See Table 5,6 and 7). We believe the less evident improvement with gradient incoherence bound compared to Synthetic data can be ascribed to the utilization of Batch Normalization.

heading: 8 Conclusion
text: We derived a novel information-theoretic analysis of the generalization property of meta-learning and provided algorithm-dependent generalization error bounds for both joint training and alternate training. Compared to previous gradient-based bounds that depend on the square norm of gradients, empirical validations on both simulated data and a few-shot benchmark show that the proposed bound is orders of magnitude tighter in most situations. Finally, we think that these theoretical results can inspire new algorithms through a deeper exploration of the relation between meta-parameters and task-parameters.
Acknowledgments and Disclosure of Funding
Work partly supported by NSERC Discovery Grant RGPIN-2016-05942 and the China Scholarship Council. We also thank SSQ Assurances and NSERC for their financial support through the Collaborative Research and Development Grant CRDPJ 529584 - 18.

Review summaries:
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. Then, 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. Finally, 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.

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.

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.

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.