# Generalization Bounds For Meta-Learning:
An Information-Theoretic Analysis

Qi Chen
Université Laval
&Changjian Shui
Université Laval
&Mario Marchand
Université Laval
<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

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 learning-to-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, 5, 6, 7, 8, 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, 12, 13, 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 meta-learning 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 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 meta-learning 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.

##  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 [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, 22, 23, 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].

##  3 Preliminaries

#### Basic Notations

We use upper case letters, e.g. $X,Y$, to denote random variables and
corresponding calligraphic letters $\mathcal{X},\mathcal{Y}$ to denote the
sets which they are defined on. We denote as $P_{X}$, the marginal probability
distribution of $X$. Given the Markov chain $X\rightarrow Y$, $P_{Y|X}$
denotes the conditional distribution or the Markov transition kernel.
$X\perp\\!\\!\\!\perp Y$ means $X$ and $Y$ are independent.

And let us recall some basic definitions:

######  Definition 3.1.

Let $\psi_{X}(\lambda)\overset{{\rm\mbox{\tiny
def}}}{=}\log\mathbb{E}[e^{\lambda(X-\mathbb{E}[X])}]$ denote the cumulant
generating function(CGF) of random variable $X$. Then $X$ is said to be
$\sigma$-subgaussian if we have

$\psi_{X}(\lambda)\leq\frac{\lambda^{2}\sigma^{2}}{2},\forall\lambda\in\mathbb{R}\,.$

######  Definition 3.2.

Let $X$, $Y$ and $Z$ be arbitrary random variables, and let $D_{\text{KL}}$
denote the KL divergence. The mutual information between $X$ and $Y$ is
defined as:

$I(X;Y)\overset{{\rm\mbox{\tiny
def}}}{=}D_{\text{KL}}(P_{X,Y}||P_{X}P_{Y})\,.$

The disintegrated mutual information between $X$ and $Y$ given $Z$ is defined
as:

$I^{Z}(X;Y)\overset{{\rm\mbox{\tiny
def}}}{=}D_{\text{KL}}(P_{X,Y|Z}||P_{X|Z}P_{Y|Z})\,.$

The corresponding conditional mutual information is defined as:

$I(X;Y|Z)\overset{{\rm\mbox{\tiny def}}}{=}\mathbb{E}_{Z}[I^{Z}(X;Y)]\,.$

#### Information theoretic bound for single task learning

We consider an unknown distribution $\mu$ on an instance space
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, and a set of independent samples
$S=\\{Z_{i}\\}_{i=1}^{m}$ drawn from $\mu$: $Z_{i}\sim\mu$ and $S\sim\mu^{m}$.
Given a parametrized hypothesis space $\mathcal{W}$ and a loss function
$\ell:\mathcal{W}\times\mathcal{Z}\rightarrow R$, the true risk and the
empirical risk of $w\in{\mathcal{W}}$ are respectively defined as
$R_{\mu}(w)\overset{{\rm\mbox{\tiny def}}}{=}\mathbb{E}_{Z\sim\mu}\ell(w,Z)$
and $R_{S}(w)\overset{{\rm\mbox{\tiny
def}}}{=}(1/m)\sum_{i=1}^{m}\ell(w,Z_{i})$.

Following the setting of information-theoretic learning [36, 15, 37], a
learning algorithm $\mathcal{A}$ is a randomized mapping that takes a dataset
$S$ as input and outputs a hypothesis $W$ according to a conditional
distribution $P_{W|S}$, i.e., $W=\mathcal{A}(S)\sim P_{W|S}$.111Note that the
conditional distribution $P_{W|S}$ is different from the posterior
distribution in Bayes learning. The (mean) generalization error
$\text{gen}(\mu,\mathcal{A})\overset{{\rm\mbox{\tiny
def}}}{=}\mathbb{E}_{W,S}[R_{\mu}(W)-R_{S}(W)]$ of an algorithm $\mathcal{A}$
is then bounded according to:

######  Theorem 3.1.

(Xu and Raginsky [15]) Suppose that for each $w\in\mathcal{W}$, the prediction
loss $\ell(w,Z)$ is $\sigma$-subgaussian with respect to $Z\sim\mu$. Then for
any randomized learner $\mathcal{A}$ characterized by $P_{W|S}$, for
$S\sim\mu^{m}$, we have

$|\text{gen}(\mu,\mathcal{A})|\leq\sqrt{\frac{2\sigma^{2}}{m}I(W;S)}\,.$

$I(W;S)$ is the mutual information between the input and output of algorithm
${\mathcal{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.

##  4 Problem Setup

Following [11], we assume that all tasks originate from a common _environment_
$\tau$, which is a probability measure on the set of probability measures on
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$. The draw of $\mu\sim\tau$
represents encountering a learning task $\mu$ in the environment $\tau$. To
run a learning algorithm for a task, we need to draw a set of data samples
from $\mu$. 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 $\tau$ induces a mixture distribution $\mu_{m,\tau}$ on
$\mathcal{Z}^{m}$ such that
$\mu_{m,\tau}(A)=\mathbb{E}_{\mu\sim\tau}[\mu^{m}{(A)}],\forall
A\subseteq\mathcal{Z}^{m}$. Thus the $m$ data points in $S$ that are
independently sampled from a random task $\mu$ encountered in $\tau$ is
denoted as $S\sim\mu_{m,\tau}$.

Consequently, for $n$ train tasks that are independently sampled from the
environment $\tau$, each train data set is denoted as $S_{i}\sim\mu_{m,\tau}$
for $i\in[n]$. Analogously, for $k$ test tasks data sets, we denote
$S^{\text{te}}_{i}\sim\mu_{m,\tau}$ for each $i\in[k]$. We further denote the
(full) training set as $S_{1:n}=(S_{1},...,S_{n})$ and the (full) testing set
as $S^{\text{te}}_{1:k}=(S^{\text{te}}_{1},...,S^{\text{te}}_{k})$.

### Meta Learner & Base Learner

Since different tasks are assumed to be an i.i.d. sampling from $\tau$, they
should share some common information. We use a _meta parameter_
$U\in\mathcal{U}$ to represent this shared knowledge. We also denote by
$W_{1:n}=(W_{1},\dots,W_{n})$ the _task specific parameters_ , where each
$W_{i}\in\mathcal{W},\forall i\in[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, $\mathcal{U}=\mathcal{W}$) for a gradient-
descent base learner.

We define the _meta learner_ $\mathcal{A}_{\text{meta}}$ as an algorithm that
takes the data sets $S_{1:n}$ as input, and then outputs a random meta-
parameter $U=\mathcal{A}_{\text{meta}}(S_{1:n})\sim P_{U|S_{1:n}}$, which is a
distribution that characterizes $\mathcal{A}_{\text{meta}}$. When learning a
new task, the base learner $\mathcal{A}_{\text{base}}$ uses a new data set
$S\sim\mu_{m,\tau}$ and the estimated meta-parameter $U$ to output a
stochastic predictor $W=\mathcal{A}_{\text{base}}(U,S)\sim
P_{W|U,S}$.222Although the base learner is the same, $P_{W_{i}|U,S_{i}}$ is
different for each task $i$ due to the different data set $S_{i}$.

To evaluate the quality of the meta information $U$ for learning a _new task_
, we define the _true meta risk_ , given the base learner
$\mathcal{A}_{\text{base}}$, as

$R_{\tau}(U)\overset{{\rm\mbox{\tiny
def}}}{=}\mathbb{E}_{S\sim\mu_{m,\tau}}\mathbb{E}_{W\sim
P_{W|S,U}}[R_{\mu}(W)]\,.$

### Joint Training & Alternate Training

Since $\tau$ and $\mu$ 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.

(a) Joint Training

(b) Alternate Training

Figure 1: Parameter updating strategy through noisy iterative approach.

For _Joint Training_ [1, 12], the whole dataset $S_{1:n}$ is used to jointly
evaluate all the parameters $(U,W_{1:n})$ in parallel. A similar training
protocol is illustrated in Fig. 1(a). Then the corresponding _empirical meta
risk_ w.r.t. $U$ is defined as:

$R_{S_{1:n}}(U)\overset{{\rm\mbox{\tiny
def}}}{=}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{W_{i}\sim
P_{W_{i}|S_{i},U}}[R_{S_{i}}(W_{i})].$

For _Alternate training_ , used in modern deep meta-learning algorithms [2],
$S_{i}$ is randomly split into two smaller datasets: a meta-train set
$S^{\text{tr}}_{i}$ with $|S^{\text{tr}}_{i}|=m_{\text{tr}}$ and a meta-
validation set $S^{\text{va}}_{i}$ with $|S^{\text{va}}_{i}|=m_{\text{va}}$
examples for each $i\in[n]$. In few-shot learning, $S_{1:n}^{\text{tr}}$ and
$S_{1:n}^{\text{va}}$ are denoted as the support set and query set.
Additionally, we have $m=m_{\text{tr}}+m_{\text{va}}$ and
$S_{i}^{\text{tr}}\perp\\!\\!\\!\perp S_{i}^{\text{va}}$. An example of the
training protocol is illustrated in Fig. 1(b), where $(U,W_{1:n})$ are
alternately updated through $S^{\text{va}}_{1:n}$ and $S^{\text{tr}}_{1:n}$,
respectively. The corresponding _empirical meta risk_ w.r.t $U$ is defined as:

$\tilde{R}_{S_{1:n}}(U)\overset{{\rm\mbox{\tiny
def}}}{=}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{W_{i}\sim
P_{W_{i}|S^{\text{tr}}_{i},U}}[R_{S^{\text{va}}_{i}}(W_{i})]\,$

Then, the _meta generalization error_ within these two modes w.r.t.
$\mathcal{A}_{\text{meta}}$ and $\mathcal{A}_{\text{base}}$ are respectively
defined as

$\text{gen}^{\text{joi}}_{\text{meta}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})\
\overset{{\rm\mbox{\tiny def}}}{=}\
\mathbb{E}_{U,S_{1:n}}[R_{\tau}(U)-R_{S_{1:n}}(U)],$

$\text{gen}^{\text{alt}}_{\text{meta}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})\
\overset{{\rm\mbox{\tiny def}}}{=}\
\mathbb{E}_{U,S_{1:n}}[R_{\tau}(U)-\tilde{R}_{S_{1:n}}(U)]\,.$

##  5 Information-Theoretic 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 theoretical results are valid for
any _randomized_ algorithm $\mathcal{A}_{\text{meta}}$ and
$\mathcal{A}_{\text{base}}$. 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 $\ell(Z,w)$, which is $\sigma$-subgaussian
for each $w\in\mathcal{W}$, where $Z\sim\mu,\mu\sim\tau$. Then, the meta
generalization error for joint training is upper bounded by

$|\text{gen}^{\text{joi}}_{\text{meta}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})|\leq\sqrt{\frac{2\sigma^{2}}{nm}I(U,W_{1:n};S_{1: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

$\sqrt{\frac{2\sigma^{2}}{mn}\left(I(U;S_{1:n})+\sum_{i=1}^{n}I(W_{i};S_{i}|U)\right)}\leq\sqrt{\frac{2\sigma^{2}}{mn}I(U;S_{1:n})}+\sqrt{\frac{2\sigma^{2}}{mn}\sum_{i=1}^{n}I(W_{i};S_{i}|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\to\infty$) 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)\geq
I(W;S|U)\approx\frac{1}{n}\sum_{i=1}^{n}I(W_{i};S_{i}|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 $\tau$, it is hard to estimate and minimize [42]. By
introducing an arbitrary distribution-free prior $Q$ on
$\mathcal{U}\times\mathcal{W}^{n}$, we can upper bound
$I(U,W_{1:n};S_{1:n})\leq
I(U,W_{1:n};S_{1:n})+D_{\text{KL}}(P_{U,W_{1:n}}||Q)=\mathbb{E}_{S_{1:n}}D_{\text{KL}}(P_{U,W_{1:n}|S_{1:n}}||Q)$
(see Lemma A.1.1). If we set a joint prior
$Q=\mathcal{P}\times\prod_{i=1}^{n}P$, then the bound of Theorem 5.1 becomes
similar to the one proposed by [1], where $\mathcal{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.

###  5.2 Conditional Mutual Information (CMI) Bound for Alternate Training

######  Theorem 5.2.

Assume that all the tasks use the same loss function $\ell(Z,w)$, which is
$\sigma$-subgaussian for each $w\in\mathcal{W}$, where
$Z\sim\mu,\mu\sim\tau$.Then we have

$|\text{gen}^{\text{alt}}_{\text{meta}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})|\leq\mathbb{E}_{S^{\text{tr}}_{1:n}}\sqrt{\frac{2\sigma^{2}I^{S^{\text{tr}}_{1:n}}(U,W_{1:n};S^{\text{va}}_{1:n})}{nm_{\text{va}}}}\leq\sqrt{\frac{2\sigma^{2}I(U,W_{1:n};S^{va}_{1:n}|S^{tr}_{1:n})}{nm_{\text{va}}}}\,.$

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.3.
Additionally, we can apply the chain rule on the conditional mutual
information, to obtain the following decomposition:

$I(U,W_{1:n};S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n})=I(U;S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n})+\sum_{i=1}^{n}I(W_{i};S^{\text{va}}_{i}|U,S^{tr}_{i})$

$=\mathbb{E}_{S_{1:n}}D_{\text{KL}}(P_{U|S_{1:n}}||P_{U|S^{\text{tr}}_{1:n}})+\mathbb{E}_{U,S_{1:n}}\sum_{i=1}^{n}D_{\text{KL}}(P_{W_{i}|S_{i},U}||P_{W_{i}|S^{\text{tr}}_{i},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.
$S_{1:n}^{tr}$, 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 $m_{\text{va}}$. If
$m_{\text{va}}$ is large, then the denominator in the bound is large. However,
since $m_{\text{va}}=m-m_{\text{tr}}$,
$D_{\text{KL}}(P_{U|S_{1:n}}||P_{U|S^{\text{tr}}_{1:n}})$ and
$D_{\text{KL}}(P_{W_{i}|S_{i},U}||P_{W_{i}|S^{\text{tr}}_{i},U})$ will also
become large since smaller $m_{\text{tr}}$ will lead to less reliable outputs.

##  6 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 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.

###  6.1 Bound for Joint Training with Bounded Gradient

In joint training, the meta and base parameters are updated simultaneously. We
denote $\Phi\overset{{\rm\mbox{\tiny
def}}}{=}(U,W_{1:n})\in\mathcal{U}\times\mathcal{W}^{n}$,
$\mathcal{U}\subseteq{\mathbb{R}}^{k},\mathcal{W}\subseteq{\mathbb{R}}^{d}$.
The training strategy is illustrated in Fig 1(a). Concretely, the learning
algorithm executes $T$ iterations. We further denote $\Phi^{t}$ as the updated
parameter at iteration $t\in[T]$, with $\Phi^{0}$ being a random
initialization.

At iteration $t\in[T]$ and for task $i\in[n]$, we randomly sample a batch
$B_{i}^{t}\subseteq S_{i}$ of size $b$ and an isotropic Gaussian noise
$\xi^{t}\sim N(0,\sigma_{t}^{2}\mathbb{I}_{(nd+k)})$. Let
$\xi^{t}=(\xi^{t}_{0},\dots,\xi^{t}_{n})$, where $\xi^{t}_{0}\in\mathcal{U}$,
and $\xi^{t}_{i}\in{\mathcal{W}},~{}\forall i\in[n]$. Then the updating rule
at iteration $t$ can be expressed as

$\Phi^{t}=\Phi^{t-1}-\eta_{t}G(\Phi^{t-1},B^{t}_{1:n})+\xi^{t}\,,$

where $G$ is the gradient of the empirical meta-risk on $B^{t}_{1:n}$ w.r.t.
all the parameters $\Phi$, and where $\eta_{t}$ is the learning rate. In
addition, we assume bounded gradients:

Assumption 2 The gradients are bounded, i.e., $\sup\limits_{\Phi\in
R^{(nd+k)},s\in\mathcal{Z}^{bn}}||G(\Phi,s)||_{2}\leq 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(\Phi;S_{1:n})\leq\sum_{t=1}^{T}\frac{nd+k}{2}\log(1+\frac{\eta_{t}^{2}L^{2}}{(nd+k)\sigma_{t}^{2}})\,.$

Specifically, if $\sigma_{t}=\sqrt{\eta_{t}}$, and $\eta_{t}=\frac{c}{t}$ for
$c>0$, we have:

$|\text{gen}_{\text{meta}}^{\text{joi}}(\tau,\mathcal{A}_{meta},\mathcal{A}_{base})|\leq\frac{\sigma
L}{\sqrt{nm}}\sqrt{c\log T+c}\,.$

See the proof in Appendix B.4. It is worth mentioning that Amit and Meir [1]
used
$\mathcal{U}\subseteq{\mathbb{R}}^{2d},\mathcal{W}\subseteq{\mathbb{R}}^{d}$.
They adopt a similar variational form of our mutual information bound, where
they use a factorized Gaussian
$Q_{\theta}=\mathcal{N}(\theta,\mathbb{I}_{2d})$ to approximate
$P_{U|S_{1:n}}$ and $Q_{\phi_{i}}=\mathcal{N}(\mu_{i},\sigma^{2}_{i})$ to
approximate $P_{W_{i}|U,S_{i}}$. They set
$P_{U}=\mathcal{N}(0,\mathbb{I}_{2d})$, and
$P_{W_{i}|U}=\mathcal{N}(\mu_{P},\sigma^{2}_{P})$, where
$(\mu_{P},\sigma^{2}_{P})\sim Q_{\theta}$. Then they optimize the meta
empirical risk plus the bound w.r.t. the parameters
$\theta\in{\mathbb{R}}^{2d}$ and
$(\mu_{i},\sigma^{2}_{i})\in{\mathbb{R}}^{2d}$ 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 is illustrated in Fig. 1(b). We
also use SGLD for the meta learner $\mathcal{A}_{\text{meta}}$ and base
learner $\mathcal{A}_{\text{base}}$, and denote this algorithm by Meta-SGLD.
To build a connection with MAML, we consider the scenarios with
$\mathcal{U}=\mathcal{W}\subseteq{\mathbb{R}}^{d}$, where meta-parameter $U$
is a common initialization for the task parameters $W_{1: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\in[T]$, there exists several parallel inner loops, where
each loop is a $K$-iteration SGLD to update different task-specific parameters
$W_{i}$.

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\in[T]$, we sample a mini-batch of tasks that are indexed by
$I_{t}\subseteq[n]$. Then the corresponding meta-train and meta-validation
data sets are denoted as $B^{\text{tr}}_{I_{t}}$ and $B^{\text{va}}_{I_{t}}$,
respectively. The task specific parameters are denoted as
$W_{I_{t}}=\\{W_{i}:i\in I_{t}\\}$. In addition, an isotropic Gaussian noise
$\xi^{t}\sim\mathcal{N}(\mathbf{0},\sigma_{t}^{2}\mathbb{I}_{d})$ is also
injected during the update. Then, the update rule w.r.t. $U$ is expressed as:

$U^{t}=U^{t-1}-\eta_{t}\nabla\tilde{R}_{B^{\text{va}}_{I_{t}}}(U^{t-1})+\xi^{t}\,,$

where $\tilde{R}_{B^{\text{va}}_{I_{t}}}(U^{t-1})=\frac{1}{|I_{t}|}\sum_{i\in
I_{t}}\mathbb{E}_{W_{i}\sim
P_{W_{i}|B^{\text{tr}}_{i,t},U^{t-1}}}[R_{B^{\text{va}}_{i,t}}(W_{i})]$ is the
empirical meta risk evaluated on $B^{\text{va}}_{I_{t}}$, and $\eta_{t}$ is
the meta learning rate at $t$. In addition, we denote the _gradient
incoherence_ of meta parameter $U$ at iteration $t$ as
$\epsilon_{t}^{u}\overset{{\rm\mbox{\tiny
def}}}{=}\nabla\tilde{R}_{B_{I_{t}}}(U^{t-1})-\nabla\tilde{R}_{B^{\text{tr}}_{I_{t}}}(U^{t-1})$.

Inner Loop Updates

Given the outer loop iteration $t$, for each inner iteration $k\in[K]$, we
randomly sample a batch of data for task $i\in I_{t}$ from
$B^{\text{tr}}_{i,t}$ (the $i$-th task in $B^{\text{tr}}_{I_{t}}$), which is
denoted as $B^{\text{tr}}_{i,t,k}$. Then the update rules for the task
parameters can be formulated as:

$W^{0}_{i,t}=U^{t-1}\,,W_{i,t}^{k}=W^{k-1}_{i,t}-\beta_{t,k}\nabla
R_{B^{\text{tr}}_{i,t,k}}(W^{k-1}_{i,t})+\zeta^{t,k}\,,$

where $\beta_{t,k}$ is the learning rate for task parameter,
$\zeta^{t,k}\sim\mathcal{N}(\mathbf{0},\sigma_{t,k}^{2}\mathbb{I}_{d})$ 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_{i,t}^{k}$. We first sample a batch $B_{i,t,k}$ from
$B^{\text{va}}_{i,t}\bigcup B^{\text{tr}}_{i,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: $\epsilon_{t,i,k}^{w}\overset{{\rm\mbox{\tiny def}}}{=}\nabla
R_{B_{i,t,k}}(W^{k-1}_{i,t})-\nabla R_{B^{\text{tr}}_{i,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:
$\tilde{R}_{B^{\text{va}}_{I_{t}}}(U^{t-1})=\frac{1}{|I_{t}|}\sum_{i\in
I_{t}}R_{B^{\text{va}}_{i,t}}(W^{K}_{i,t})=\frac{1}{|I_{t}|}\sum_{i\in
I_{t}}R_{B^{\text{va}}_{i,t}}(U^{t-1}-\beta_{t,1}\nabla
R_{B^{\text{tr}}_{i,t,1}}(U^{t-1}))\,,$ and $\frac{1}{|I_{t}|}\sum_{i\in
I_{t}}\nabla R_{B^{\text{va}}_{i,t}}(W_{i,t}^{K})$ 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
$\sigma_{t}=\sqrt{2\eta_{t}/\gamma_{t}}$,
$\sigma_{t,k}=\sqrt{2\beta_{t,k}/\gamma_{t,k}}$, where $\gamma_{t}$ and
$\gamma_{t,k}$ are the inverse temperatures. The meta generalization error for
alternate training satisfies

$|\text{gen}^{\text{alt}}_{\text{meta}}(\tau,\text{SGLD},\text{SGLD})|\leq\sqrt{\frac{2\sigma^{2}I(U,W_{1:n};S^{va}_{1:n}|S^{tr}_{1:n})}{nm_{\text{va}}}}\
\leq\ \frac{\sigma}{\sqrt{nm_{\text{va}}}}\sqrt{\epsilon_{U}+\epsilon_{W}}\,,$

where

$\epsilon_{U}=\sum_{t=1}^{T}\mathbb{E}_{B^{va}_{I_{t}},B^{tr}_{I_{t}},W_{I_{t}},U^{t-1}}\frac{\eta_{t}\gamma_{t}\|\epsilon_{t}^{u}\|^{2}_{2}}{2},~{}~{}~{}~{}\epsilon_{W}=\sum_{t=1}^{T}\sum_{i=1}^{|I_{t}|}\sum_{k=1}^{K}\mathbb{E}_{{B^{va}_{i,t,k},B^{tr}_{i,t,k},W_{i,t}^{k-1}}}\frac{\beta_{t,k}\gamma_{t,k}\|\epsilon_{t,i,k}^{w}\|^{2}_{2}}{2}\,.$

The proof is provided in Appendix B.5. The bound of Theorem 6.2 consists of
two parts: $\epsilon_{U}$, which reflects the generalization error bound of
the meta learner, and $\epsilon_{W}$, which reflects the generalization bound
of the base learner. Moreover, $\epsilon_{U}$ and $\epsilon_{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
$\eta_{t}=\frac{1}{t},\beta_{t,k}=\frac{1}{tk}$, the meta generalization error
bound is in $\mathcal{O}(\sqrt{c_{1}\log T+c_{2}\log K})$, where $c_{1},c_{2}$
are some constants. In contrast, when learning rates are fixed, the bound is
in $\mathcal{O}(\sqrt{c_{1}T+c_{2}TK})$.

##  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.333Code is
available at: https://github.com/livreQ/meta-sgld.

###  7.1 Synthetic Data

We consider a simple example of 2D mean estimation to illustrate the meta-
learning setup. We assume that the environment $\tau$ is a truncated 2D
Gaussian distribution $\mathcal{N}((-4,-4)^{T},5\mathbb{I}_{2})$. A new task
is also defined as a 2D Gaussian $\mathcal{N}(\mu,0.1\mathbb{I}_{2})$ with
$\mu\sim\tau$. To generate few-shot tasks, we sample $n=20000$ tasks from the
environment with $\mu_{i}\sim\tau,\forall i\in[n]$. After sampling $\mu_{i}$
for each task, we further sample $m=16$ data points from
$\mathcal{N}(\mu_{i},0.1\mathbb{I}_{2})$. At each iteration $t$, we randomly
choose a subset of $5$ tasks ($|I_{t}|=5$) from the whole data set. We
evaluate on three different few-shot settings with
$m_{\text{va}}=\\{1,8,15\\}$ and the corresponding train size
$m_{\text{tr}}=\\{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
$\sigma\sqrt{\frac{\epsilon_{U}}{nm_{\text{va}}}}$ (Fig. 2(a)) and
$\sigma\sqrt{\frac{\epsilon_{W}}{nm_{\text{va}}}}$ (Fig. 2(b)). The
expectation terms within the bound are estimated via Monte-Carlo sampling. To
compare the conventional Lipschiz bound with 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
$m_{\text{va}}=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
$m_{\text{tr}}$) 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
$m_{\text{tr}}=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).

(a) Bound of 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-incoherence (G_Inco) in different few-shot
settings.

###  7.2 Few-Shot Benchmark

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=\tbinom{1200}{5}$ tasks. At each epoch, we have trained the model with
$|I_{t}|=32$ tasks. Analogous to the simulated data, we have conducted our
experiment with $m_{\text{tr}}=\\{15,8,1\\}$ and $m_{\text{va}}=\\{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 $m_{\text{tr}}=8,15$. In
particular, the gradient-incoherence bound w.r.t. $U$ is much tighter than the
gradient-norm bound when $m_{\text{tr}}=15$, which illustrates the benefits of
the proposed theory. Simultaneously, the gradient-incoherence bound is similar
to the gradient-norm bound when $m_{\text{tr}}=1$, illustrating a theoretical
limitation of learning with very few meta-train samples. Moreover, we observe
that the optimal values for $m_{\rm{va}}$ depends on the environment since the
tightest bound for Omniglot is achieved with $m_{\text{va}}=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.

(a) Bound of U

(b) Bound of W

Figure 3: Omniglot: Estimation of the generalization-error 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

##  8 Conclusion

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.

## References

  * Amit and Meir [2018] 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.
  * Finn et al. [2017] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _ICML_ , 2017.
  * Thrun and Pratt [1998] Sebastian Thrun and Lorien Pratt.  Learning to learn: Introduction and overview.  In _Learning to learn_ , pages 3–17. Springer, 1998.
  * Liu et al. [2018] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ , 2018.
  * Brown et al. [2020] 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.14165_ , 2020.
  * Garcia and Bruna [2017] Victor Garcia and Joan Bruna.  Few-shot learning with graph neural networks.  _arXiv preprint arXiv:1711.04043_ , 2017.
  * Ravi and Beatson [2018] Sachin Ravi and Alex Beatson.  Amortized bayesian meta-learning.  In _International Conference on Learning Representations_ , 2018.
  * Snell et al. [2017] Jake Snell, Kevin Swersky, and Richard Zemel.  Prototypical networks for few-shot learning.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pages 4080–4090, 2017.
  * Sung et al. [2018] 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–1208, 2018.
  * Ravi and Larochelle [2016] Sachin Ravi and Hugo Larochelle.  Optimization as a model for few-shot learning.  In _International Conference on Learning Representations_ , 2016.
  * Baxter [2000] Jonathan Baxter.  A model of inductive bias learning.  _Journal of artificial intelligence research_ , 12:149–198, 2000.
  * Pentina and Lampert [2014] Anastasia Pentina and Christoph Lampert.  A pac-bayesian bound for lifelong learning.  In _International Conference on Machine Learning_ , pages 991–999, 2014.
  * Denevi et al. [2019a] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil.  Learning-to-learn stochastic gradient descent with biased regularization.  In _International Conference on Machine Learning_ , pages 1566–1575. PMLR, 2019a.
  * Balcan et al. [2019] 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.
  * Xu and Raginsky [2017] Aolin Xu and Maxim Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  In _Advances in Neural Information Processing Systems_ , pages 2524–2533, 2017.
  * Yoon et al. [2018] 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.
  * Scaman and Virmaux [2018] Kevin Scaman and Aladin Virmaux.  Lipschitz regularity of deep neural networks: analysis and efficient estimation.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 3839–3848, 2018.
  * Li et al. [2019] Jian Li, Xuanyuan Luo, and Mingda Qiao.  On generalization error bounds of noisy gradient methods for non-convex learning.  _arXiv preprint arXiv:1902.00621_ , 2019.
  * Welling and Teh [2011] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 681–688, 2011.
  * Jose and Simeone [2020] Sharu Theresa Jose and Osvaldo Simeone.  Information-theoretic generalization bounds for meta-learning and applications.  _arXiv preprint arXiv:2005.04372_ , 2020.
  * Jiang et al. [2019] Yihan Jiang, Jakub Konečnỳ, Keith Rush, and Sreeram Kannan.  Improving federated learning personalization via model agnostic meta learning.  _arXiv preprint arXiv:1909.12488_ , 2019.
  * Liu et al. [2019] 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.
  * Fallah et al. [2020a] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar.  Personalized federated learning: A meta-learning approach.  _arXiv preprint arXiv:2002.07948_ , 2020a.
  * Gui et al. [2018] 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 on Computer Vision (ECCV)_ , pages 432–450, 2018.
  * Nichol and Schulman [2018] Alex Nichol and John Schulman.  Reptile: a scalable metalearning algorithm.  _arXiv preprint arXiv:1803.02999_ , 2(3):4, 2018\.
  * Finn et al. [2018] Chelsea Finn, Kelvin Xu, and Sergey Levine.  Probabilistic model-agnostic meta-learning.  In _Advances in Neural Information Processing Systems_ , pages 9516–9527, 2018.
  * Grant et al. [2018] Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas Griffiths.  Recasting gradient-based meta-learning as hierarchical bayes.  In _International Conference on Learning Representations_ , 2018.
  * Khodak et al. [2019] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar.  Adaptive gradient-based meta-learning methods.  _arXiv preprint arXiv:1906.02717_ , 2019.
  * Denevi et al. [2019b] Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil.  Online-within-online meta-learning.  In _ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019)_ , volume 32, pages 1–11. Neural Information Processing Systems (NeurIPS 2019), 2019b.
  * Finn et al. [2019] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine.  Online meta-learning.  In _International Conference on Machine Learning_ , pages 1920–1930. PMLR, 2019.
  * Fallah et al. [2020b] 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 Statistics_ , pages 1082–1092. PMLR, 2020b.
  * Ji et al. [2020] Kaiyi Ji, Junjie Yang, and Yingbin Liang.  Multi-step model-agnostic meta-learning: Convergence and improved algorithms.  _arXiv preprint arXiv:2002.07836_ , 2020.
  * Denevi et al. [2018] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil.  Learning to learn around a common mean.  In _ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 31 (NIPS 2018)_ , volume 31. NIPS Proceedings, 2018.
  * Bai et al. [2021] Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lee, Sham Kakade, Huan Wang, and Caiming Xiong.  How important is the train-validation split in meta-learning?  In _International Conference on Machine Learning_ , pages 543–553. PMLR, 2021.
  * Saunshi et al. [2021] Nikunj Saunshi, Arushi Gupta, and Wei Hu.  A representation learning perspective on the importance of train-validation splitting in meta-learning.  In _International Conference on Machine Learning_ , pages 9333–9343. PMLR, 2021.
  * Russo and Zou [2019] 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–323, 2019.
  * Bu et al. [2020] Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli.  Tightening mutual information-based bounds on generalization error.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):121–130, 2020.
  * Pensia et al. [2018] 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.
  * Negrea et al. [2019] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy.  Information-theoretic generalization bounds for sgld via data-dependent estimates.  In _Advances in Neural Information Processing Systems_ , pages 11015–11025, 2019.
  * Steinke and Zakynthinou [2020] Thomas Steinke and Lydia Zakynthinou.  Reasoning about generalization via conditional mutual information.  _arXiv preprint arXiv:2001.09122_ , 2020.
  * Maurer et al. [2016] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes.  The benefit of multitask representation learning.  _The Journal of Machine Learning Research_ , 17(1):2853–2884, 2016.
  * McAllester and Stratos [2020] David McAllester and Karl Stratos.  Formal limitations on the measurement of mutual information.  In _International Conference on Artificial Intelligence and Statistics_ , pages 875–884. PMLR, 2020.
  * Raginsky et al. [2017] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky.  Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.  In _Conference on Learning Theory_ , pages 1674–1703. PMLR, 2017\.
  * Lake et al. [2011] Brenden Lake, Ruslan Salakhutdinov, Jason Gross, and Joshua Tenenbaum.  One shot learning of simple visual concepts.  In _Proceedings of the annual meeting of the cognitive science society_ , volume 33, 2011.
  * Vinyals et al. [2016] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra.  Matching networks for one shot learning.  _arXiv preprint arXiv:1606.04080_ , 2016.
  * Boucheron et al. [2013] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration inequalities: A nonasymptotic theory of independence_.  Oxford university press, 2013.
  * Germain et al. [2016] Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien.  Pac-bayesian theory meets bayesian inference.  In _Advances in Neural Information Processing Systems_ , pages 1884–1892, 2016.
  * Long [2018] Liangqu Long.  Maml-pytorch implementation.  https://github.com/dragen1860/MAML-Pytorch, 2018.
  * Amit [2019] Ron Amit.  meta-learning-adjusting-priors.  https://github.com/ron-amit/meta-learning-adjusting-priors2, 2019\.

##  Appendix A Technical Lemmas

######  Lemma A.1 (Variational Form of Mutual Information).

Let $X$ and $Y$ be two random variables. For all probability measures $Q$
defined on the space of $X$, we have

$I(X;Y)\leq E_{Y}[D_{\text{KL}}(P_{X|Y}||Q)],$

with equality for $Q=P_{X}$.

###### Proof.

$\displaystyle I(X;Y)+D_{\text{KL}}(P_{X}||Q)$ $\displaystyle=\iint
p(x,y)\log\frac{p(x,y)}{p(x)p(y)}dxdy+\int p(x)\log\frac{p(x)}{q(x)}dx$
$\displaystyle=\iint p(x,y)\log\frac{p(x,y)}{p(x)p(y)}dxdy+\iint
p(x,y)\log\frac{p(x)}{q(x)}dxdy$ $\displaystyle=\iint
p(x,y)\log\frac{p(x|y)}{q(x)}dxdy$
$\displaystyle=\mathbb{E}_{Y}[D_{\text{KL}}(P(X|Y)||Q)]\,.$

Since $D_{\text{KL}}(P_{X}||Q)\geq 0$, the equality exists only when
$Q=P_{X}$, which concludes the proof. ∎

######  Lemma A.2.

Let $X,Y,Z$ be random variables. For all $\mathcal{Z}$-measurable probability
measures $Q$ on the space of $X$, $I^{Z}(X;Y)\leq
E_{Y|Z}[D_{\text{KL}}(P_{X|Y,Z}||Q)]$, with equality for $Q=P_{X|Z}$.

###### Proof.

$\displaystyle I^{Z}(X;Y)+D_{\text{KL}}(P_{X|Z}||Q)$ $\displaystyle=\iint
p(x,y|z)\log\frac{p(x,y|z)}{p(x|z)p(y|z)}dxdy+\iint
p(x|z)\log\frac{p(x|z)}{q(x)}dx$ $\displaystyle=\iint
p(x,y|z)\log\frac{p(x,y|z)}{p(x|z)p(y|z)}dxdy$
$\displaystyle\quad\quad\quad\quad+\iint p(x,y|z)\log\frac{p(x|z)}{q(x)}dxdy$
$\displaystyle=\iint p(x,y|z)\log\frac{p(x|y,z)}{q(x)}dxdy$
$\displaystyle=\mathbb{E}_{Y|Z}[D_{\text{KL}}(P(X|Y,Z)||Q)]$

Since $D_{\text{KL}}(P_{X|Z}||Q)\geq 0$, the equality exists only when
$Q=P_{X|Z}$, which concludes the proof. ∎

######  Lemma A.3.

Let $X,Y,Z$ be random variables. For all $\mathcal{Z}$-measurable probability
measures $Q$ defined on the space of $X$,
$I(X;Y|Z)=\mathbb{E}_{Z}[I^{Z}(X;Y)]\leq
E_{Y,Z}[D_{\text{KL}}(P_{X|Y,Z}||Q)]$, with equality for $Q=P_{X|Z}$.

###### Proof.

Take the expectation on the inequality of Lemma B.2 to obtain the result. ∎

######  Lemma A.4.

(Donsker-Varadhan representation[Corollary 4.15[46]]) Let $P$ and $Q$ be two
probability measures defined on a set $\mathcal{X}$. Let
$g:\mathcal{X}\rightarrow R$ be a measurable function, and let
$\mathbb{E}_{x\sim Q}[\exp{g(x)}]\leq\infty$. Then

$D_{\text{KL}}(P||Q)=\sup\limits_{g}\\{\mathbb{E}_{x\sim
P}[g(x)]-\log\mathbb{E}_{x\sim Q}[\exp{g(x)}]\\}.$

######  Lemma A.5.

(Decoupling Estimate[Xu and Raginsky [15]]) Consider a pair of random
variables $X$ and $Y$ with joint distribution $P_{X,Y}$, let $\tilde{X}$ be an
independent copy of $X$, and $\tilde{Y}$ an independent copy of $Y$, such that
$P_{\tilde{X},\tilde{Y}}=P_{X}P_{Y}$. For arbitrary real-valued function
$f:\mathcal{X}\times\mathcal{Y}\rightarrow{\mathbb{R}}$, if
$f(\tilde{X},\tilde{Y})$ is $\sigma$-subgaussian under
$P_{\tilde{X},\tilde{Y}}$, then:

$|\mathbb{E}[f(X,Y)]-\mathbb{E}[f(\tilde{X},\tilde{Y})]|\leq\sqrt{2\sigma^{2}I(X;Y)}$

######  Lemma A.6.

Let Q be an arbitrary distribution on $\mathcal{W}$, and let $S$ be an
arbitrary sample of examples. The solution to the optimization problem

$P^{*}\ =\ \arg\inf\limits_{P}\left\\{\mathbb{E}_{W\sim P}[R_{S}(W)]\ +\
\frac{1}{\beta}D_{\text{KL}}(P||Q)\right\\}\,.$

is given by the Gibbs distribution

$dP^{*}(w)\ =\ \frac{e^{-\beta R_{S}(w)}dQ(w)}{\mathbb{E}_{W\sim Q}e^{-\beta
R_{S}(W)}}\,.$

######  Lemma A.7.

(Data Processing Inequality) Given random variables $X,Y,Z,V$, and the Markov
Chain:

$X\rightarrow Y\rightarrow Z,$

then we have

$I(X;Z)\leq I(X;Y)\,,I(X;Z)\leq I(Y;Z).$

For Markov chain

$V\rightarrow X\rightarrow Y\rightarrow Z\,,$

we have

$I(X;Z|V)\leq I(X;Y|V),I(X;Z|V)\leq I(Y;Z|V)$

###### Proof.

Since

$I(X;Y,Z)=I(X;Z)+I(X;Y|Z)=I(X;Y)+I(X;Z|Y)\,,$

and with the Markov Chain, we have $X\perp\\!\\!\\!\perp Z|Y$, therefore

$I(X;Z|Y)=H(X|Y)-H(X|Y,Z)=0\,.$

In addition, $I(X;Y|Z)\geq 0$, so $I(X;Z)\leq I(X;Y)$.

$I(Z;X,Y)=I(Z;X)+I(Z;Y|X)=I(Z;Y)+I(Z;X|Y)=I(Y:Z)\,,$

with $I(Y;Z|X)\geq 0$, we have $I(X;Z)\leq I(Y;Z)$.

Similarly, for the second Markov chain, we have $X\perp\\!\\!\\!\perp Z|Y,V$,
therefore

$I(X;Z|Y,V)=H(X|Y,V)-H(X|Y,Z,V)=0\,.$
$I(X;Y,Z|V)=I(X;Z|V)+I(X;Y|V,Z)=I(X;Y|V)+I(X;Z|Y,V)=I(X;Y|V)$

So we have $I(X;Z|V)\leq I(X;Y|V)$, the rest proof is similar and omitted. ∎

######  Lemma A.8.

Given random variables $X,Y,Z_{1},Z_{2}$, and the graph model:

$Z_{1}\rightarrow Z_{2}\rightarrow X\leftarrow Y\,,$

then we have

$I(X;Y|Z_{1})\leq I(X;Y|Z_{2})$

###### Proof.

Apply chain rule, we get:

$I(X;Y,Z_{2}|Z_{1})=I(X;Y|Z_{1})+I(X;Z_{2}|Y,Z_{1})=I(X;Z_{2}|Z_{1})+I(X;Y|Z_{2},Z_{1})$

From the graph model, we have $Y\perp\\!\\!\\!\perp Z_{1}$,
$Y\perp\\!\\!\\!\perp Z_{2}$ and $(X,Y)\perp\\!\\!\\!\perp Z_{1}|Z_{2}$. Hence

$I(X;Y|Z_{2},Z_{1})=H(X|Z_{2},Z_{1})-H(X|Y,Z_{2},Z_{1})=H(X|Z_{2})-H(X|Y,Z_{2})=I(X;Y|Z_{2})$

Moreover,

$\displaystyle I(X,Y;Z_{2}|Z_{1})$
$\displaystyle=I(X;Z_{2}|Z_{1})+I(Y;Z_{2}|X,Z_{1})$
$\displaystyle=I(Y;Z_{2}|Z_{1})+I(Z_{2};X|Y,Z_{1})$
$\displaystyle=I(Z_{2};X|Y,Z_{1})$

the last equality is obtained with $Y\perp\\!\\!\\!\perp Z_{2}$ and
$Y\perp\\!\\!\\!\perp Z_{1}$, since $I(Y;Z_{2}|X,Z_{1})\geq 0$, we get
$I(X;Z_{2}|Z_{1})\leq I(X;Z_{2}|Y,Z_{1})$. Consequently, we have
$I(X;Y|Z_{1})\leq I(X;Y|Z_{2})$, conclude the proof. ∎

##  Appendix B Proof

###  B.1 Proof of Theorem 5.1

######  Theorem (Meta-generalization error bound for joint training).

Suppose all tasks use the same loss $\ell(Z,w)$, which is $\sigma$-subgaussian
for any $w\in\mathcal{W}$, where $Z\sim\mu,\mu\sim\tau$.Then, the meta
generalization error for joint training is upper bounded by

$|\text{gen}^{\text{joi}}_{\text{meta}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})|\leq\sqrt{\frac{2\sigma^{2}}{nm}I(U,W_{1:n};S_{1:n})}\,.$

###### Proof.

In contrast to previous works [12, 1, 20], which separately bound the
environment-level and task-level error and then combine the two terms, we
consider $U,W_{1:n}$ as a collection and directly bound the whole term. By
using the chain rule for mutual information, the final result can then be
split into an environment-level and a task-level contribution.

Similar to Lemma 2.5, let
$\Phi=(U,W_{1:n})\in\mathcal{U}\times\mathcal{W}^{n}$ be a collection of
random variables such that $\Phi\not\perp\\!\\!\\!\perp S_{1:n}$, and let
$\tilde{\Phi}=(\tilde{U},\tilde{W}_{1:n})\in\mathcal{U}\times\mathcal{W}^{n}$
be an in dependant copy of $\Phi$ such that $\tilde{\Phi}\perp\\!\\!\\!\perp
S_{1:n}$, i.e., $\tilde{\Phi}$ is distributed according to
$P_{U,W_{1:n}}=\mathbb{E}_{S_{1:n}}P_{U,W_{1:n}|S_{1:n}}$. Let

$f(\Phi,S_{1:n})\overset{{\rm\mbox{\tiny
def}}}{=}\frac{1}{n}\sum_{i=1}^{n}[R_{S_{i}}(W_{i})]=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m}\sum_{j=1}^{m}\ell(W_{i},Z_{i,j}).$

For any $\lambda\in{\mathbb{R}}$, let

$\displaystyle\psi_{\tilde{\Phi},S_{1:n}}(\lambda)$
$\displaystyle\overset{{\rm\mbox{\tiny
def}}}{=}\log\mathbb{E}_{\tilde{\Phi},S_{1:n}}\left[e^{\lambda(f(\tilde{\Phi},S_{1:n})-\mathbb{E}[f(\tilde{\Phi},S_{1:n})]}\right]$
$\displaystyle=\log\mathbb{E}_{\tilde{\Phi},S_{1:n}}[e^{\lambda
f(\tilde{\Phi},S_{1:n})}]-\lambda\mathbb{E}_{\tilde{\Phi},S_{1:n}}[f(\tilde{\Phi},S_{1:n})]\,.$

Moreover,

$\displaystyle I(\Phi;S_{1:n})$
$\displaystyle=D_{\text{KL}}(P_{\Phi,S_{1:n}}||P_{\Phi}P_{S_{1:n}})$
$\displaystyle=\sup\limits_{g}\left\\{\mathbb{E}_{\Phi,S_{1:n}}[g(\Phi,S_{1:n})]-\log\mathbb{E}_{\tilde{\Phi},S_{1:n}}[e^{g(\tilde{\Phi},S_{1:n})}]\right\\}$
$\displaystyle\geq\lambda\mathbb{E}_{\Phi,S_{1:n}}[f(\Phi,S_{1:n})]-\log\mathbb{E}_{\tilde{\Phi},S_{1:n}}[e^{\lambda
f(\tilde{\Phi},S_{1:n})}]\,,\quad\forall\lambda\in{\mathbb{R}}$
$\displaystyle=\lambda\mathbb{E}_{U,W_{1:n},S_{1:n}}[f(\Phi,S_{1:n})]-\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n},S_{1:n}}[f(\tilde{\Phi},S_{1:n})]-\psi_{\tilde{\Phi},S_{1:n}}(\lambda)$
$\displaystyle=\lambda\mathbb{E}_{U,W_{1:n},S_{1:n}}\frac{1}{n}\sum_{i=1}^{n}[R_{S_{i}}(W_{i})]-\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n},S_{1:n}}\frac{1}{n}\sum_{i=1}^{n}[R_{S_{i}}(\tilde{W}_{i})]-\psi_{\tilde{\Phi},S_{1:n}}(\lambda)$
(1)

Since $(W_{i},S_{i}),i=1,...,n$ are mutually independent given $U$, and
$S_{1},...S_{n}$ are independent, we have
$p(w_{1:n}|s_{1:n},u)=\prod_{i=1}^{n}p(w_{i}|s_{i},u)$. Hence

$\displaystyle\lambda\mathbb{E}_{U,W_{1:n},S_{1:n}}\frac{1}{n}\sum_{i=1}^{n}[R_{S_{i}}(W_{i})]$
$\displaystyle=\lambda\mathbb{E}_{U,S_{1:n}}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{W_{i}|S_{i},U}[R_{S_{i}}(W_{i})]$
$\displaystyle=\lambda\mathbb{E}_{U,S_{1:n}}[R_{S_{1:n}}(U)]$ (2)

Since $\tilde{\Phi}\perp\\!\\!\\!\perp S_{1:n}$, we have that
$P_{\tilde{W}_{1:n}|S_{1:n},\tilde{U}}=P_{\tilde{W}_{1:n}|\tilde{U}}$ and
$P_{\tilde{W}_{1:n},S_{1:n},\tilde{U}}=P_{\tilde{W}_{1:n},\tilde{U}}P_{S_{1:n}}$.
Hence,

$\displaystyle R_{\tau}(\tilde{U})$
$\displaystyle=\mathbb{E}_{S\sim\mu_{m,\tau}}\mathbb{E}_{\tilde{W}\sim
P_{\tilde{W}|S,\tilde{U}}}[R_{\mu}(\tilde{W})]=\mathbb{E}_{\mu\sim\tau}\mathbb{E}_{S|\mu\sim\mu^{m}}\mathbb{E}_{\tilde{W}\sim
P_{\tilde{W}|\tilde{U}}}[R_{\mu}(\tilde{W})]$
$\displaystyle=\mathbb{E}_{\mu\sim\tau}\mathbb{E}_{\tilde{W}\sim
P_{\tilde{W}|\tilde{U}}}[R_{\mu}(\tilde{W})]\,.$

Therefore

$\displaystyle\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n},S_{1:n}}\frac{1}{n}\sum_{i=1}^{n}R_{S_{i}}(\tilde{W}_{i})$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}}\mathbb{E}_{S_{1:n}\sim\mu_{m,\tau}^{n}}\left[\frac{1}{n}\sum_{i=1}^{n}R_{S_{i}}(\tilde{W}_{i})\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S_{i}\sim\mu_{m,\tau}}R_{S_{i}}(\tilde{W}_{i})\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mu_{i}\sim\tau}\mathbb{E}_{S_{i}|\mu_{i}\sim\mu_{i}^{m}}R_{S_{i}}(\tilde{W}_{i})\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mu_{i}\sim\tau}\left[\frac{1}{m}\sum_{j=1}^{m}\mathbb{E}_{Z_{i,j}\sim\mu_{i}}\ell(\tilde{W}_{i},Z_{i,j})\right]\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U}}\mathbb{E}_{\tilde{W}_{1:n}|\tilde{U}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mu_{i}\sim\tau}\left[\frac{1}{m}\sum_{j=1}^{m}\mathbb{E}_{Z_{i,j}\sim\mu_{i}}\ell(\tilde{W}_{i},Z_{i,j})\right]\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\tilde{W}_{i}|\tilde{U}}\mathbb{E}_{\mu_{i}\sim\tau}R_{\mu_{i}}(\tilde{W}_{i})\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U}}\mathbb{E}_{\mu\sim\tau}\mathbb{E}_{\tilde{W}|\tilde{U}}R_{\mu}(\tilde{W})=\lambda\mathbb{E}_{\tilde{U}}R_{\tau}(\tilde{U})$
$\displaystyle=\lambda\mathbb{E}_{U,S_{1:n}}R_{\tau}(U)\,.$ (3)

If we use Equations (2) and (3), then Equation (1) becomes

$-\lambda{\mathbb{E}}_{U,S_{1:n}}\left[R_{\tau}(U)-R_{S_{1:n}}(U)\right]\
\leq\
I(\Phi;S_{1:n})+\psi_{\tilde{\Phi},S_{1:n}}(\lambda)\,,\quad\forall\lambda\in{\mathbb{R}}.$
(4)

Since this inequality is also valid when $\lambda$ is negative, this implies
that we also have

${\mathbb{E}}_{U,S_{1:n}}\left[R_{\tau}(U)-R_{S_{1:n}}(U)\right]\leq\frac{1}{\lambda}\left[I(\Phi;S_{1:n})+\psi_{\tilde{\Phi},S_{1:n}}(-\lambda)\right]\,,\quad\forall\lambda>0\,.$

Consequently,

$\text{gen}_{\text{meta}}^{\text{joi}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})\
\leq\
\frac{1}{\lambda}\left[I(\Phi;S_{1:n})+\psi_{\tilde{\Phi},S_{1:n}}(-\lambda)\right]\,,\quad\forall\lambda>0\,.$

Since $\ell(\tilde{W},Z)$ is $\sigma$-subgaussian, we have that
$f(\tilde{\Phi},S_{1:n})=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m}\sum_{j=1}^{m}\ell(\tilde{W}_{i},Z_{i,j})$
is $\frac{\sigma}{\sqrt{nm}}$-subgaussian.444More discussion on subgaussianity
can be found in Section C. Hence,

$\psi_{\tilde{\Phi},S_{1:n}}(\lambda)\ \leq\
\frac{\lambda^{2}\sigma^{2}}{2nm}\quad\forall\lambda\in{\mathbb{R}}\,.$

Thus, we have

$\text{gen}_{\text{meta}}^{\text{joi}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})\
\leq\
\frac{I(\Phi;S_{1:n})}{\lambda}+\frac{\lambda\sigma^{2}}{2nm}\,,\quad\forall\lambda>0\,.$

By using the value of $\lambda$ that minimizes the r.h.s. of the above
equation, we have

$\text{gen}_{\text{meta}}^{\text{joi}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})\leq\sqrt{\frac{2\sigma^{2}I(\Phi;S_{1:n})}{nm}}\,.$
(5)

Returning to Equation (4), we have for $\lambda>0$:

${\mathbb{E}}_{U,S_{1:n}}\left[R_{\tau}(U)-R_{S_{1:n}}(U)\right]\geq-\frac{1}{\lambda}\left[I(\Phi;S_{1:n})+\psi_{\tilde{\Phi},S_{1:n}}(\lambda)\right]\geq-\sqrt{\frac{2\sigma^{2}I(\Phi;S_{1:n})}{nm}}\,.$

Hence, we also have

$\text{gen}_{\text{meta}}^{\text{joi}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})\geq-\sqrt{\frac{2\sigma^{2}I(\Phi;S_{1:n})}{nm}}\,.$
(6)

Then, Equations (5) and (6) together imply that

$\left|\text{gen}_{\text{meta}}^{\text{joi}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})\right|\leq\sqrt{\frac{2\sigma^{2}I(\Phi;S_{1:n})}{nm}}\,,$

which gives the theorem. ∎

###  B.2 Benefits of Meta Learning

The task specific empirical risk $R_{S}(W)$ is independent of the meta
parameter $U$, given the task specific parameter $W$, which gives the implicit
independence assumption $S\perp\\!\\!\\!\perp U|W$. We thus have $I(U;S|W)=0$,
and the following two possible decompositions:

$I(S;U,W)=I(W;S|U)+I(U;S)=I(W;S)+I(U;S|W)=I(W;S)\,.$

Since $I(U;S)\geq 0$, we obtain $I(W;S|U)\leq I(W;S)$.

As mentioned in the main paper, Theorem 5.1 can cover the PAC Bayes bound of
Amit and Meir [1] with the variational form of mutual information. Their work
has built a connection between PAC Bayes meta-learning and Hierarchical
Variational Bayes. In Appendix A.3 of [1], they give the generative graph
model for meta learning where $U\rightarrow W\rightarrow S$ (their notation
used $\psi$ instead of $U$). They assumed that $S$ is independent of $U$ given
$W$, in Bayes learning, this implies that $p(S|W,U)=p(S|W)$. Based on the
graph model, they obtained a similar optimization objective as their PAC-Bayes
meta learning algorithm, which minimizes the expected empirical risk plus the
PAC Bayes bound. Germain et al. [47] has given a more obvious connection
between PAC Bayes learning and Bayes learning, where optimizing the PAC Bayes
bound together with the expected empirical risk gives the so called Gibbs
algorithm (see Lemma A.6.6). When using the negative log loss, i.e.,
$R_{S}(W)=-\frac{1}{m}\log p(S|W)=-\frac{1}{m}\sum_{i=1}^{m}\log p(Z_{i}|W)$,
the output of Gibbs algorithm coincides with the Bayes Posterior. Therefore,
without the independence assumption, $R_{S}(W)$ should be defined as
$R_{S}(W,U)$, which corresponds to $-\frac{1}{m}\log p(S|W,U)$ in Bayes
learning.

###  B.3 Proof of Theorem 5.2

######  Theorem (Meta-generalization error bound for alternate training).

Suppose all tasks use the same loss $\ell(Z,w)$, which is $\sigma$-subgaussian
for any $w\in\mathcal{W}$, where $Z\sim\mu,\mu\sim\tau$. Then we have

$|\text{gen}^{\text{alt}}_{\text{meta}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})|\leq\mathbb{E}_{S^{\text{tr}}_{1:n}}\sqrt{\frac{2\sigma^{2}I^{S^{\text{tr}}_{1:n}}(U,W_{1:n};S^{\text{va}}_{1:n})}{nm_{\text{va}}}}\leq\sqrt{\frac{2\sigma^{2}I(U,W_{1:n};S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n})}{nm_{\text{va}}}}\,.$

###### Proof.

The proof technique is analogous to Theorem 5.1. Let $\Phi=(U,W_{1:n})$ be a
collection of random variables where $\Phi\in\mathcal{U}\times\mathcal{W}^{n}$
such that $\Phi$ and $S_{1:n}$ follow the joint distribution
$P_{\Phi,S_{1;n}}$. Then let $\tilde{\Phi}$ be an independent copy of $\Phi$,
such that
$\tilde{\Phi}\perp\\!\\!\\!\perp\\{S^{\text{va}}_{1:n},S_{1:n}^{\text{tr}}\\}$,
i.e., $\tilde{\Phi}\sim\mathbb{E}_{S_{1:n}}P_{\Phi|S_{1:n}}$. Define

$f(\Phi,S^{\text{va}}_{1:n})=\frac{1}{n}\sum_{i=1}^{n}[R_{S^{\text{va}}_{i}}(W_{i})]=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m}\sum_{j=1}^{m_{\text{va}}}\ell(W_{i},Z_{i,j})\,.$

For any $\lambda\in{\mathbb{R}}$, denote the cumulant generation function of
$\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}$ as:

$\displaystyle\psi_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}(\lambda)$
$\displaystyle=\log\mathbb{E}_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[e^{\lambda(f(\tilde{\Phi},S^{\text{va}}_{1:n})-\mathbb{E}_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[f(\tilde{\Phi},S^{\text{va}}_{1:n})]}]$
$\displaystyle=\log\mathbb{E}_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[e^{\lambda
f(\tilde{\Phi},S^{\text{va}}_{1:n})}]-\lambda\mathbb{E}_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[f(\tilde{\Phi},S^{\text{va}}_{1:n})]$

In addition, the disintegrated mutual information is given as:

$\displaystyle I^{S^{\text{tr}}_{1:n}}(\Phi;S^{\text{va}}_{1:n})$
$\displaystyle=D_{\text{KL}}(P_{\Phi,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}||P_{\tilde{\Phi}|S^{\text{tr}}_{1:n}}P_{S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}})$
$\displaystyle=\sup\limits_{g}\left\\{\mathbb{E}_{\Phi,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[g(\Phi,S^{\text{va}}_{1:n})]-\log\mathbb{E}_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}\left[e^{g(\tilde{\Phi},S^{\text{va}}_{1:n})}\right]\right\\}$
$\displaystyle\geq\lambda\mathbb{E}_{\Phi,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[f(\Phi,S^{\text{va}}_{1:n})]-\log\mathbb{E}_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}\left[e^{\lambda
f(\tilde{\Phi},S^{\text{va}}_{1:n})}\right]$
$\displaystyle=\lambda\mathbb{E}_{U,W_{1:n},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[f(\Phi,S^{\text{va}}_{1:n})]$
$\displaystyle\quad\quad\quad\quad\quad\quad-\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[f(\tilde{\Phi},S^{\text{va}}_{1:n})]-\psi_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}(\lambda)$
$\displaystyle=\lambda\mathbb{E}_{U,W_{1:n},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}\frac{1}{n}\sum_{i=1}^{n}R_{S^{\text{va}}_{i}}(W_{i})$
$\displaystyle\quad\quad\quad\quad\quad\quad-\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}\frac{1}{n}\sum_{i=1}^{n}R_{S^{\text{va}}_{i}}(\tilde{W}_{i})-\psi_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}(\lambda)$
(7)

Since given $U$, $(W_{i},S^{\text{tr}}_{i}),i=1,...,n$ are mutually
independent, we have
$p(w_{1:n}|s^{\text{tr}}_{1:n},u)=\prod_{i=1}^{n}p(w_{i}|s^{\text{tr}}_{i},u)$.
Thus

$\displaystyle\lambda\mathbb{E}_{U,W_{1:n},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}\frac{1}{n}\sum_{i=1}^{n}[R_{S^{\text{va}}_{i}}(W_{i})]$
$\displaystyle=\lambda\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{W_{i}|S^{\text{tr}}_{i},U}[R_{S^{\text{va}}_{i}}(W_{i})]$
$\displaystyle=\lambda\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[\tilde{R}_{S_{1:n}}(U)]$
(8)

Since we have
$\tilde{\Phi}\perp\\!\\!\\!\perp\\{S^{\text{va}}_{1:n},S_{1:n}^{\text{tr}}\\}$,
thus $P_{\tilde{W}_{1:n}|S_{1:n},\tilde{U}}=P_{\tilde{W}_{1:n}|\tilde{U}}$, we
have:

$\displaystyle R_{\tau}(\tilde{U})$
$\displaystyle=\mathbb{E}_{S\sim\mu_{m,\tau}}\mathbb{E}_{\tilde{W}\sim
P_{\tilde{W}|S,\tilde{U}}}[R_{\mu}(\tilde{W})]=\mathbb{E}_{\mu\sim\tau}\mathbb{E}_{S|\mu\sim\mu^{m}}\mathbb{E}_{\tilde{W}\sim
P_{\tilde{W}|\tilde{U}}}[R_{\mu}(\tilde{W})]$
$\displaystyle=\mathbb{E}_{\mu\sim\tau}\mathbb{E}_{\tilde{W}\sim
P_{\tilde{W}|\tilde{U}}}[R_{\mu}(\tilde{W})]$

Moreover, we have $S_{1:n}^{\text{tr}}\perp\\!\\!\\!\perp
S_{1:n}^{\text{va}}$, so that
$P_{\tilde{W}_{1:n},S^{\text{va}}_{1:n},\tilde{U}|S_{1:n}^{\text{tr}}}=P_{\tilde{W}_{1:n},\tilde{U}}P_{S^{\text{va}}_{1:n}|S_{1:n}^{\text{tr}}}=P_{\tilde{W}_{1:n},\tilde{U}}P_{S^{\text{va}}_{1:n}}$.
Then we can also prove:

$\displaystyle\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}$
$\displaystyle\left[\frac{1}{n}\sum_{i=1}^{n}R_{S^{\text{va}}_{i}}(\tilde{W}_{i})\right]=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}|S^{\text{tr}}_{1:n}}\mathbb{E}_{S^{\text{va}}_{1:n}\sim\mu_{m_{\text{va}},\tau}^{n}}\left[\frac{1}{n}\sum_{i=1}^{n}R_{S_{i}^{\text{va}}}(\tilde{W}_{i})\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}|S^{\text{tr}}_{1:n}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S_{i}\sim\mu_{m_{\text{va}},\tau}}R_{S^{\text{va}}_{i}}(\tilde{W}_{i})\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}|S^{\text{tr}}_{1:n}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mu_{i}\sim\tau}\mathbb{E}_{S_{i}|\mu_{i}\sim\mu_{i}^{m_{\text{va}}}}[R_{S^{\text{va}}_{i}}(\tilde{W}_{i})]\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U},\tilde{W}_{1:n}|S^{\text{tr}}_{1:n}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mu_{i}\sim\tau}[\frac{1}{m_{\text{va}}}\sum_{j=1}^{m_{\text{va}}}\mathbb{E}_{Z_{i,j}\sim\mu_{i}}\ell(\tilde{W}_{i},Z_{i,j})]\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U}|S_{1:n}^{\text{tr}}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\tilde{W}_{i}|\tilde{U}}\mathbb{E}_{\mu_{i}\sim\tau}[\frac{1}{m_{\text{va}}}\sum_{j=1}^{m_{\text{va}}}\mathbb{E}_{Z_{i,j}\sim\mu_{i}}\ell(\tilde{W}_{i},Z_{i,j})]\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U}|S_{1:n}^{\text{tr}}}\left[\mathbb{E}_{\mu\sim\tau}\mathbb{E}_{\tilde{W}|\tilde{U}}[R_{\mu}(\tilde{W})]\right]$
$\displaystyle=\lambda\mathbb{E}_{\tilde{U}|S_{1:n}^{\text{tr}}}R_{\tau}(\tilde{U})=\lambda\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}R_{\tau}(U)$
(9)

Therefore, by combining Equations (7), (8), and (9), we have for any
$\lambda$,

$\lambda\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[\tilde{R}_{S_{1:n}}(U)]-\lambda\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[R_{\tau}(U)]\leq
I^{S^{\text{tr}}_{1:n}}(\Phi;S^{\text{va}}_{1:n})+\psi_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}(\lambda)$

Since $\ell(\tilde{W},Z)$ is $\sigma$-subgaussian, and
$\tilde{\Phi}\perp\\!\\!\\!\perp{S^{\text{va}}_{1:n}}$,
$f(\tilde{\Phi},S^{\text{va}}_{1:n})=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m_{\text{va}}}\sum_{j=1}^{m_{\text{va}}}\ell(\tilde{W}_{i},Z_{ij})$
is $\frac{\sigma}{\sqrt{nm_{\text{va}}}}$-subgaussian. Hence,
$\psi_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}(\lambda)\leq\frac{\lambda^{2}\sigma^{2}}{2nm_{\text{va}}},\forall\lambda\in{\mathbb{R}}$.
For $\lambda<0$ we have

$\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[R_{\tau}(U)-\tilde{R}_{S_{1:n}}(U)]\leq\frac{I^{S^{\text{tr}}_{1:n}}(\Phi;S^{\text{va}}_{1:n})+\psi_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}(\lambda)}{-\lambda}\leq\sqrt{\frac{2\sigma^{2}I^{S^{\text{tr}}_{1:n}}(\Phi;S^{\text{va}}_{1:n})}{nm_{\text{va}}}}$

Similarly, for $\lambda>0$ we have

$\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[R_{\tau}(U)-\tilde{R}_{S_{1:n}}(U)]\geq\frac{I^{S^{\text{tr}}_{1:n}}(\Phi;S^{\text{va}}_{1:n})+\psi_{\tilde{\Phi},S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}(\lambda)}{-\lambda}\geq-\sqrt{\frac{2\sigma^{2}I^{S^{\text{tr}}_{1:n}}(\Phi;S^{\text{va}}_{1:n})}{nm_{\text{va}}}}$

Then, the following concludes the proof:

$|\text{gen}_{\text{meta}}^{\text{alt}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})|=\mathbb{E}_{S^{\text{tr}}_{1:n}}|\mathbb{E}_{U,S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}}[R_{\tau}(U)-\tilde{R}_{S_{1:n}}(U)]|\leq\mathbb{E}_{S^{\text{tr}}_{1:n}}\sqrt{\frac{2\sigma^{2}I^{S^{\text{tr}}_{1:n}}(\Phi;S^{\text{va}}_{1:n})}{nm_{\text{va}}}}$

∎

###  B.4 Proof of Theorem 6.1

######  Theorem.

Based on Theorem 5.1, for the SGLD algorithm that satisfies Assumptions 1 & 2,
the mutual information for joint training satisfies

$I(\Phi;S_{1:n})\leq\sum_{t=1}^{T}\frac{nd+k}{2}\log(1+\frac{\eta_{t}^{2}L^{2}}{(nd+k)\sigma_{t}^{2}})\,.$

Specifically, if $\sigma_{t}=\sqrt{\eta_{t}}$, and $\eta_{t}=\frac{c}{t}$ for
$c>0$, we have:

$|\text{gen}_{\text{meta}}^{\text{joi}}(\tau,\mathcal{A}_{meta},\mathcal{A}_{base})|\leq\frac{\sigma
L}{\sqrt{nm}}\sqrt{c\log T+c}\,.$

###### Proof.

Define the sequence of parameters for $T$ iterations as
$\Phi^{[T]}\overset{{\rm\mbox{\tiny def}}}{=}(\Phi^{1},...,\Phi^{T})$ and the
corresponding sequence of samplings as $B_{1:n}^{[T]}\overset{{\rm\mbox{\tiny
def}}}{=}(B_{1:n}^{1},...,B_{1:n}^{T})$. The output of the algorithm is
defined as $\Phi=f(\Phi^{[T]})$, which can be the last iterate $\Phi^{T}$ or
the average output $\frac{1}{T}\sum_{t=1}^{T}\Phi^{t}$. From the figure about
the parameter updating strategy for joint training illustrated in Section 6,
we get the following Markov chain:

$S_{1:n}\rightarrow B_{1:n}^{[T]}\rightarrow\Phi^{[T]}\rightarrow\Phi\,.$

Therefore, by applying Lemma A.7.7 to the above Markov chain, we have:

$I(\Phi;S_{1:n})\leq I(\Phi^{[T]};S_{1:n})\leq
I(\Phi^{[T]};B^{[T]}_{1:n})=\sum_{t=1}^{T}I(\Phi^{t};B^{[T]}_{1:n}|\Phi^{[t-1]})\,.$

The last equality comes from the mutual information chain rule. Combing the
sample strategy with Assumption 1 and the update rule, we obtain:

$\displaystyle I(\Phi^{t};B^{[T]}_{1:n}|\Phi^{[t-1]})$
$\displaystyle=I(\Phi^{t};B^{t}_{1:n}|\Phi^{t-1})$
$\displaystyle=h(\Phi^{t}|\Phi^{t-1})-h(\Phi^{t}|\Phi^{t-1},B^{t}_{1:n})\,.$

Conditioned on $\Phi^{t-1}=\phi^{t-1}$, we have
$\Phi^{t}=\phi^{t-1}-\eta_{t}G(\phi^{t-1},B^{t}_{1:n})+\xi^{t}$. Then

$h(\Phi^{t}-\phi^{t-1}|\Phi^{t-1}=\phi^{t-1})=h(\Phi^{t}|\Phi^{t-1}=\phi^{t-1})\,.$

Note that $\xi^{t}$ and $\eta_{t}G(\phi^{t-1},B^{t}_{1:n})$ are independent.
So we have

$\mathbb{E}(||\Phi^{t}-\phi^{t-1}||_{2}^{2})=\mathbb{E}(||\eta_{t}G(\phi^{t-1},B^{t}_{1:n})||_{2}^{2}+||\xi^{t}||_{2}^{2})\leq\eta_{t}^{2}L^{2}+(nd+k)\sigma_{t}^{2}\,.$

The Gaussian distribution is the one having the largest entropy among the
variables with the same second order moment. Hence,

$h(\Phi^{t}|\Phi^{t-1}=\phi^{t-1})\leq\frac{nd+k}{2}\log(2\pi
e\frac{\eta_{t}^{2}L^{2}+(nd+k)\sigma_{t}^{2}}{(nd+k)})$

for all $\phi^{t-1}$.

In addition,

$\displaystyle h(\Phi^{t}|\Phi^{t-1},B^{t}_{1:n})$
$\displaystyle=h(\Phi^{t-1}-\eta_{t}G(\Phi^{t-1},B^{t}_{1:n})+\xi^{t}|\Phi^{t-1},B^{t}_{1:n})$
$\displaystyle=h(\xi^{t})=\frac{nd+k}{2}\log 2\pi e\sigma_{t}^{2}.$

So we obtain

$I(\Phi;S_{1:n})\leq\sum_{t=1}^{T}\frac{nd+k}{2}\log(1+\frac{\eta_{t}^{2}L^{2}}{(nd+k)\sigma_{t}^{2}})\leq\sum_{t=1}^{T}\frac{\eta_{t}^{2}L^{2}}{2\sigma_{t}^{2}}.$

Hence, for the SGLD algorithm with $\sigma_{t}=\sqrt{\eta_{t}}$, constant
$c>0$, $\eta_{t}=\frac{c}{t}$; since $\sum_{t=1}^{T}\frac{1}{t}\leq\log T+1$,
we have

$\displaystyle|\text{gen}^{\text{joi}}_{\text{meta}}(\tau,\mathcal{A}_{\text{meta}},\mathcal{A}_{\text{base}})|$
$\displaystyle\leq\sqrt{\frac{2\sigma^{2}(I(U,W_{1:n};S_{1:n}))}{nm}}$
$\displaystyle\leq\sqrt{\frac{\sigma^{2}}{nm}\sum_{t=1}^{T}\frac{\eta_{t}^{2}L^{2}}{2\sigma_{t}^{2}}}$
$\displaystyle\leq\frac{\sigma L}{\sqrt{nm}}\sqrt{c\log T+c}\,.$

∎

###  B.5 Proof of Theorem 6.2

######  Theorem.

Based on Theorem 5.2, for the Meta-SGLD that satisfies Assumption 1, if we set
$\sigma_{t}=\sqrt{2\eta_{t}/\gamma_{t}}$,
$\sigma_{t,k}=\sqrt{2\beta_{t,k}/\gamma_{t,k}}$, where $\gamma_{t}$ and
$\gamma_{t,k}$ are the inverse temperatures. The meta generalization error for
alternate training satisfies

$|\text{gen}^{\text{alt}}_{\text{meta}}(\tau,\text{SGLD},\text{SGLD})|\leq\sqrt{\frac{2\sigma^{2}I(U,W_{1:n};S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n})}{nm_{\text{va}}}}\
\leq\ \frac{\sigma}{\sqrt{nm_{\text{va}}}}\sqrt{\epsilon_{U}+\epsilon_{W}}\,,$

where

$\epsilon_{U}=\sum_{t=1}^{T}\mathbb{E}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},W_{I_{t}},U^{t-1}}\frac{\eta_{t}\gamma_{t}\|\epsilon_{t}^{u}\|^{2}_{2}}{2},~{}~{}~{}~{}\epsilon_{W}=\sum_{t=1}^{T}\sum_{i=1}^{|I_{t}|}\sum_{k=1}^{K}\mathbb{E}_{{B^{\text{va}}_{i,t,k},B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1}}}\frac{\beta_{t,k}\gamma_{t,k}\|\epsilon_{t,i,k}^{w}\|^{2}_{2}}{2}\,.$

###### Proof.

To prove the above theorem, we need to introduce some basic notations to
present the sampling results and the intermediate output of each gradient
step, by which we can apply the Markov structure and the mutual information
chain rule.

  * •

for $K$ inner iterations:

    * –

The sequence of validation data samplings at outer iteration $t$ for task $i$
and the task batch:

$B_{i,t,[K]}^{\text{\text{va}}}=(B_{i,t,1}^{\text{va}},...,B_{i,t,K}^{\text{va}}),B_{I_{t},[K]}^{\text{va}}=(B_{1,t,[K]}^{\text{va}},...,B_{|I_{t}|,t,[K]}^{\text{va}})$

    * –

The sequence of train data samplings at outer iteration $t$ for task $i$ and
the task batch:

$B_{i,t,[K]}^{\text{tr}}=(B_{i,t,1}^{\text{tr}},...,B_{i,t,K}^{\text{tr}}),B_{I_{t},[K]}^{\text{tr}}=(B_{1,t,[K]}^{\text{tr}},...,B_{|I_{t}|,t,[K]}^{\text{tr}})$

    * –

the sequence of task specific parameters at outer iteration $t$ of task $i$
and the task batch:

$W_{i,t}^{[K]}=(W_{i,t}^{1},...,W_{i,t}^{K}),W_{I_{t}}^{[K]}=(W_{1,t}^{[K]},...,W_{|I_{t}|,t}^{[K]})\,;$

    * –

The output of base learner at outer iteration $t$ of task $i$ and the task
batch:

$W_{i,t}=g(W_{i,t}^{[K]}),W_{I_{t}}=(W_{1,t},...,W_{|I_{t}|,t})$

  * •

for $T$ outer iterations:

    * –

The sequence of meta parameters as $U^{[T]}=(U^{1},...,U^{T})$;

    * –

validation data sequences as
$B_{I_{[T]}}^{\text{va}}=(B_{I_{1}}^{\text{va}},...,B_{I_{T}}^{\text{va}})$;

    * –

train data sequences as
$B_{I_{[T]}}^{\text{tr}}=(B_{I_{1}}^{\text{tr}},...,B_{I_{T}}^{\text{tr}})$;

    * –

Output of meta learner is defined as $U=f(U^{[T]})$;

    * –

Output sequence of base learner is defines as
$W_{I_{[T]}}=(W_{I_{1}},...,W_{I_{T}})$

Based on the definition above, we have the following Markov chains:

$\displaystyle S_{1:n}^{\text{va}}\rightarrow
B^{\text{va}}_{I_{[T]}}\rightarrow U^{[T]}\rightarrow U$ (10) $\displaystyle
S_{1:n}^{\text{tr}}\rightarrow B^{\text{tr}}_{I{[T]}}\rightarrow
W_{I_{[T]}}\rightarrow W_{1:n}$ (11) $\displaystyle
B^{\text{tr}}_{I_{t}}\rightarrow B^{\text{tr}}_{I_{t},[K]}\rightarrow
W_{I_{t}}^{[K]}\rightarrow W_{I_{t}}$ (12) $\displaystyle
B^{\text{tr}}_{i,t}\rightarrow B^{\text{tr}}_{i,t,[K]}\rightarrow
W_{i,t}^{[K]}\rightarrow W_{i,t}$ (13)

And the graph model:

$\displaystyle S_{1:n}^{\text{tr}}\rightarrow
B^{\text{tr}}_{I{[T]}}\rightarrow(W_{I_{[T]}},U^{[T]})\leftarrow
S_{1:n}^{\text{va}}$ (14)

In fact, the algorithm has a nest-loop structure, we just list the above
simple sub-structures for the first step of the proof. By combining the above
Markov chains and the independence of the sample strategy, we obtain

$\displaystyle I(U,W_{1:n};S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n})$
$\displaystyle\leq
I(U^{[T]},W_{1:n};S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n})\leq
I(U^{[T]},W_{I_{[T]}};S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n})$
$\displaystyle\leq
I(U^{[T]},W_{I_{[T]}};S^{\text{va}}_{1:n}|B^{\text{tr}}_{I_{[T]}})\leq
I(U^{[T]},W_{I_{[T]}};B^{\text{va}}_{I_{[T]}}|B^{\text{tr}}_{I_{[T]}})$ (15)

Apply Lemma A.7.7, the first and the last inequality are obtained with Markov
chain (10). The second inequality is obtained with (11). The third inequality
comes from Lemma A.8.8 and the graph model(14).

Furthermore, we can apply (12), (13), the information chain rule together with
the updating rules, to obtain the following decomposition:

$\displaystyle I($ $\displaystyle
U^{[T]},W_{I_{[T]}};B^{\text{va}}_{I_{[T]}}|B^{\text{tr}}_{I_{[T]}})=\sum_{t=1}^{T}I(U^{t},W_{I_{t}};B^{\text{va}}_{I_{t}}|B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t-1}})$
$\displaystyle\quad\quad=\sum_{t=1}^{T}\left\\{I(W_{I_{t}};B^{\text{va}}_{I_{t}}|B^{\text{tr}}_{I_{t}},U^{t-1})+I(U^{t};B^{\text{va}}_{I_{t}}|B^{\text{tr}}_{I_{t}},W_{I_{t}},U^{t-1})\right\\}$
$\displaystyle\quad\quad\leq\sum_{t=1}^{T}\left\\{\sum_{i=1}^{b}\left[I(W_{i,t}^{[K]};B^{\text{va}}_{i,t}|B^{\text{tr}}_{i,t},U^{t-1})\right]+I(U^{t};B^{\text{va}}_{I_{t}}|B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}})\right\\}$
$\displaystyle\quad\quad\leq\sum_{t=1}^{T}\sum_{i=1}^{b}\sum_{k=1}^{K}I(W_{i,t}^{k};B^{\text{va}}_{i,t,k}|U^{t-1},B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1})+\sum_{t=1}^{T}I(U^{t};B^{\text{va}}_{I_{t}}|B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}})$
$\displaystyle\quad\quad=\sum_{t=1}^{T}\sum_{i=1}^{b}\sum_{k=1}^{K}\mathbb{E}_{B^{\text{va}}_{i,t,k},B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1}}\left[D_{\text{KL}}(P_{W_{i,t}^{k}|B^{\text{tr}}_{i,t,k},B^{\text{va}}_{i,t,k},W_{i,t}^{k-1}}||P_{W_{i,t}^{k}|B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1}})\right]$
$\displaystyle\quad\quad\quad\quad+\sum_{t=1}^{T}\mathbb{E}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},U^{t-1}}\left[D_{\text{KL}}(P_{U^{t}|B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}}}||P_{U^{t}|B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}}})\right]\,.$
(16)

######  Remark.

Here, the KL divergence is for every single iteration, it’s not for the full
trajectory. In addition, the randomness brought by sampling and previous
updates is implied by the expectation. To empirically evaluate the bound, we
can sample the variables presented in the expectation to compute the KL
divergence.

Recall the following updates rules:

$\displaystyle W^{k}_{i,t}=W^{k-1}_{i,t}-\beta_{t,k}\nabla
R_{B^{\text{tr}}_{i,t,k}}(W^{k-1}_{i,t})+\zeta^{t,k}$ $\displaystyle
U^{t}=U^{t-1}-\eta_{t}\nabla\tilde{R}_{B^{\text{va}}_{I_{t}}}(U^{t-1})+\xi^{t}\,.$

For the SGLD algorithm, we use the typical choices of
$\sigma_{t}=\sqrt{2\eta_{t}/\gamma_{t}}$,
$\zeta_{k}=\sqrt{2\beta_{t,k}/\gamma_{t,k}}$, where $\gamma_{t}$ and
$\gamma_{t,k}$ are the inverse temperatures. Then, the update rules give

$\displaystyle
P_{U^{t}|B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}}}\sim\mathcal{N}(U^{t-1}-\eta_{t}\nabla\tilde{R}_{B^{\text{tr}}_{I_{t}}}(U^{t-1}),\frac{2\eta_{t}}{\gamma_{t}})$
$\displaystyle
P_{U^{t}|B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}}}\sim\mathcal{N}(U^{t-1}-\eta_{t}\nabla\tilde{R}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}}}(U^{t-1}),\frac{2\eta_{t}}{\gamma_{t}})$
$\displaystyle
P_{W_{i,t}^{k}|B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1}}\sim\mathcal{N}(W_{i,t}^{k-1}-\beta_{t,k}\nabla
R_{B^{\text{tr}}_{i,t,k}}(W^{k-1}_{i,t}),\frac{2\beta_{t,k}}{\gamma_{t,k}})$
$\displaystyle
P_{W_{i,t}^{k}|B^{\text{tr}}_{i,t,k},B^{\text{va}}_{i,t,k},W_{i,t}^{k-1}}\sim\mathcal{N}(W_{i,t}^{k-1}-\beta_{t,k}\nabla
R_{B^{\text{tr}}_{i,t,k},B^{\text{va}}_{i,t,k}}(W^{k-1}_{i,t}),\frac{2\beta_{t,k}}{\gamma_{t,k}})$

Let
$\epsilon_{t}^{u}=\nabla\tilde{R}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}}}(U^{t-1})-\nabla\tilde{R}_{B^{\text{tr}}_{I_{t}}}(U^{t-1})$,
then we have

$\displaystyle
D_{\text{KL}}(P_{U^{t}|B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},W_{I_{t}}}||P_{U^{t}|B^{\text{tr}}_{I_{t}},W_{I_{t}}})=\frac{\eta_{t}^{2}||\epsilon_{t}^{u}||^{2}_{2}}{2\sigma_{t}^{2}}=\frac{\eta_{t}\gamma_{t}||\epsilon_{t}^{u}||^{2}_{2}}{4}$
(17)

Similarly, let $\epsilon_{t,i,k}^{w}=\nabla
R_{\tilde{B}^{\text{tr}}_{i,t,k},\tilde{B}^{\text{va}}_{i,t,k}}(W^{k-1}_{i,t})-\nabla
R_{\tilde{B}^{\text{tr}}_{i,t,k}}(W^{k-1}_{i,t})$, we have

$\displaystyle
D_{\text{KL}}(P_{W_{i,t}^{k}|W_{i,t}^{k-1},B^{\text{va}}_{i,t,k},B^{\text{tr}}_{i,t,k}}||P_{W_{i,t}^{k}|W_{i,t}^{k-1},B^{\text{tr}}_{i,t,k}})=\frac{\beta_{t,k}\gamma_{t,k}||\epsilon_{t,i,k}^{w}||^{2}_{2}}{4}$
(18)

Combine Theorem 5.2 and equations(15), (16), (17),(18), we have

$\displaystyle|\text{gen}^{\text{alt}}_{\text{meta}}(\tau,\text{SGLD},\text{SGLD})|\leq\sqrt{\frac{2\sigma^{2}(I(U,W_{1:n};S^{\text{va}}_{1:n}|S^{\text{tr}}_{1:n}))}{nm_{\text{va}}}}$
$\displaystyle\leq\frac{\sigma}{\sqrt{nm_{\text{va}}}}\sqrt{\sum_{t=1}^{T}\mathbb{E}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}}}\frac{\eta_{t}\gamma_{t}||\epsilon_{t}^{u}||^{2}_{2}}{2}+\sum_{t=1}^{T}\sum_{i=1}^{|I_{t}|}\sum_{k=1}^{K}\mathbb{E}_{{B^{\text{va}}_{i,t,k},B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1}}}\frac{\beta_{t}^{k}\gamma_{t}^{k}||\epsilon_{t,i,k}^{w}||^{2}_{2}}{2}}$

which concludes the proof. ∎

##  Appendix C On Subgaussianity

We list the two subgaussian assumptions of Xu and Raginsky [15] and Bu et al.
[37] respectively as follows:

Assumption (a) $\forall w\in{\mathcal{W}}$, $\ell(w,Z)$ is
$\sigma$-subgaussian for $Z\sim\mu$.

Assumption (b) $\ell(\tilde{W},Z)$ is $\sigma$-subgaussian under
$P_{\tilde{W},Z}=P_{W}\times\mu$, where $\tilde{W}$ is an independent copy of
$W$ and $\tilde{W}\perp\\!\\!\\!\perp Z$.

Xu and Raginsky [15] directly use Assumption (a) to conclude Assumption (b) in
their proof. Two counter examples have been proposed to challenge this
conclusion in Appendix section C of [39] and section IV of [37]. However, we
notice that these two counterexamples are based on the case of unbounded loss
with no constraint on the parameter $W$ output by the learning algorithm. We
now compare the two assumptions mentioned above in detail for unbounded loss
and bounded loss.

###  C.1 unbounded loss

Counterexample for Assumption (a) => (b) (Negrea et al. [39])

Consider ${\mathcal{W}}={\mathcal{Z}}={\mathbb{R}}$ with $\ell(w,z)=w+z$.
Assume that $\tilde{W}\perp\\!\\!\\!\perp Z,\tilde{W}\sim
Cauchy,\tilde{Z}\sim{\mathcal{N}}(0,\sigma^{2})$. Thus, $\ell(w,Z)$ is
$\sigma$-subgaussian for any $w\in{\mathcal{W}}$, because
$\psi_{\ell(w,Z)}(\lambda)=\log{\mathbb{E}}_{Z}[e^{\lambda(\ell(w,Z)-{\mathbb{E}}\ell(w,Z))}]=\log{\mathbb{E}}[e^{\lambda
Z}]=\exp^{\frac{\lambda^{2}\sigma^{2}}{2}}$. While $\ell(\tilde{W},\tilde{Z})$
is not subgaussian since the Cauchy distribution does not have well-defined
moments higher than the zeroth moment.

Counterexample for Assumption (b) => (a) (Bu et al. [37])

Consider ${\mathcal{W}}={\mathcal{Z}}={\mathbb{R}}^{d}$ and the square loss
function $\ell(w,z)=\|w-z\|_{2}^{2}$. Assume
$\tilde{W}\sim{\mathcal{N}}(\mu,\sigma_{W}^{2}\mathbb{I}_{d}),Z\sim{\mathcal{N}}(\mu,\sigma^{2}_{Z}\mathbb{I}_{d})$.
Then $\ell(w,Z)$ is not subgaussian for all $w\in{\mathcal{W}}$, since when
$\|w\|_{2}^{2}\rightarrow\infty$ the variance of $\ell(w,Z)$ is not bounded.
However,
$\tilde{W}-Z\sim{\mathcal{N}}(0,(\sigma_{W}^{2}+\sigma^{2}_{Z})\mathbb{I}_{d})$,
so
$\ell(\tilde{W},\tilde{Z})=\|\tilde{W}-Z\|_{2}^{2}\sim(\sigma_{W}^{2}+\sigma^{2}_{Z})\chi^{2}_{d}$
has bounded CGF for $\lambda<0$, which can induce one-sided bound in our
theorem with $\sigma^{2}=2d(\sigma_{W}^{2}+\sigma_{Z}^{2})^{2}$. However, in
this condition, the loss is sub-exponential but not subgaussian as claimed by
Bu et al. [37] in assumption (b).

###  C.2 bounded loss

For a bounded loss function $\ell(w,z)\in[a,b]$, the two assumptions are
equivalent. $\ell(w,Z)$ is $\frac{(b-a)}{2}$-subgaussian $\forall
w\in{\mathcal{W}},Z\sim\mu$. Similarly, $\ell(W,Z)$ is
$\frac{(b-a)}{2}$-subgaussian under $P_{\tilde{W},Z}=P_{W}\times\mu$. The
counter example of [39] does not apply because the Cauchy distribution is
truncated and, consequently, has well-defined moments.

###  C.3 Discussion

Based on the above analysis, we can conclude the following. For a bounded
loss, the two assumptions are equivalent. In contrast, Assumption (b) is a
stronger assumption than Assumption (a) when the loss function is unbounded.
At the same time, we found that Assumption (b) is also hard to ensure and is
often replaced by the sub-exponential assumption as a relaxation for unbounded
loss.

What we need for proving Theorem 5.1 and 5.2 is actually the extension of
assumption (b). However, in practice, the parameters output from an algorithm
should always be bounded. Moreover, for complex data sets used in deep
learning, people often adopt a bounded loss or truncate the unbounded loss to
ensure the theoretical guarantee. The inconsistency between the two
assumptions should not cause too many problems. Hence, we extended Assumption
(a) to avoid confusion and too much discussion in the main paper, although the
more rigorous version should make use of Assumption (b).

##  Appendix D Additional Experimental Results

###  D.1 Synthetic Data

In this section, we present a more direct visualization for the 2D mean
estimation experiment described in Section 7.1. We compare the results of
three different train-validation split settings in Figure 4. The yellow cross
in the figure is the actual environment mean $(-4,-4)$. Note that we have set
the task batch size as $|I_{t}|=5$. The five clusters in the graph are the
task batch data points at the last epoch, which corresponds to five different
$\mu_{i}\sim\tau,\forall i\in[|I_{t}|]$. We use small dots to represent the
data points, and big dots to show the estimated cluster mean $W_{i}$ and the
estimated environment mean $U$.

Figure 4 illustrates that the distances from the estimated $U$ to the yellow
cross are slightly different for these three settings. When $m_{\text{va}}=1$
the estimated mean $U$ is much closer to the actual environment mean. This
result is coherent with the bound estimation results in Section 7.1, where we
got the tightest gradient incoherence bound with $m_{\text{va}}=1$. While the
gradient norm bound is largest for $m_{\text{va}}=1$, which indicates that the
gradient norm bound may not be as reliable as the gradient incoherence bound
since it may be much looser and won’t give too much information.

(a) $m_{\text{va}}=15$

(b) $m_{\text{va}}=1$

(c) $m_{\text{va}}=8$

Figure 4: Visualization for simulated data results

Comparison with the observed generalization error

We calculated the observed generalization error by evaluating the expected
difference between the train loss and test loss. And we list the results of
synthetic data under different train-validation split settings in Table 1,
Table 2 and Table 3.

Table 1: $m_{tr}=8,m_{va}=8$

epoch | 20 | 40 | 60 | 80 | 100 | 120 | 140 | 160 | 180
---|---|---|---|---|---|---|---|---|---
Train-Test gap | 0.0697 | 0.0371 | 0.0908 | 0.0241 | 0.1072 | 0.1492 | 0.1775 | 0.1432 | 0.1581
Lipschitz | 19.77 | 27.63 | 33.7 | 38.84 | 43.37 | 47.47 | 51.24 | 54.75 | 58.05
G_norm | 6.009 | 7.506 | 8.807 | 9.856 | 10.643 | 11.558 | 12.386 | 13.275 | 14.014
G_inco (Ours) | 0.251 | 0.3462 | 0.4315 | 0.4976 | 0.5529 | 0.6112 | 0.6480 | 0.6983 | 0.7424

Table 2: $m_{tr}=15,m_{va}=1$

epoch | 20 | 40 | 60 | 80 | 100 | 120 | 140 | 160 | 180
---|---|---|---|---|---|---|---|---|---
Train-Test gap | 0.06857 | 0.03689 | 0.09728 | 0.0327 | 0.1113 | 0.1628 | 0.04986 | 0.06426 | 0.1674
Lipschitz | 55.79 | 77.96 | 95.09 | 109.6 | 122.4 | 133.9 | 144.6 | 154.5 | 163.8
G_norm | 17.29 | 21.39 | 25.07 | 28.04 | 30.24 | 32.79 | 35.15 | 37.63 | 39.73
G_inco (Ours) | 0.1774 | 0.2486 | 0.3127 | 0.3661 | 0.4074 | 0.4481 | 0.4817 | 0.5182 | 0.5468

Table 3: $m_{tr}=1,m_{va}=15$

epoch | 20 | 40 | 60 | 80 | 100 | 120 | 140 | 160 | 180
---|---|---|---|---|---|---|---|---|---
Train-Test gap | 0.2389 | 0.06293 | 0.3155 | 0.1718 | 0.1822 | 0.2196 | 0.1687 | 0.1814 | 0.1923
Lipschitz | 14.21 | 19.86 | 24.22 | 27.91 | 31.17 | 34.12 | 36.83 | 39.35 | 41.72
G_norm | 4.484 | 5.579 | 6.572 | 7.363 | 7.953 | 8.632 | 9.249 | 9.899 | 10.42
G_inco (Ours) | 0.7801 | 1.048 | 1.286 | 1.45 | 1.617 | 1.76 | 1.89 | 2.018 | 2.149

Where Train-Test gap is the observed generalization error, G_inco is the whole
gradient incoherence bound, i.e:
$\sqrt{\frac{\sigma^{2}(\epsilon_{U}+\epsilon_{W})}{nm_{va}}}$, G_norm is the
corresponding bound w.r.t. gradient norm.

Thus, we can see that the gradient-incoherence bound is much closer to the
estimation of the actual gap but can be improved in the future.

###  D.2 Omniglot

Now we give additional experimental results for the deep few-shot benchmark –
Omniglot. We compare the test accuracy for Meta-SGLD with three train-
validation split settings, i.e., $m_{va}=\\{1,8,15\\}$. The test accuracy for
MAML and Meta-SGLD with $\\{0,1,4,10\\}$ fine-tune steps are illustrated in
Table 4.

Under the same experiment settings, Meta-SGLD achieves slightly better
performance than our reproduced MAML. However, our test accuracy is not
comparable to the original results of MAML [2]. We only trained the model with
2000 epochs, and the other hyper-parameter settings are also different from
[2]. Moreover, our Meta-SGLD code is modified based on [48]. This realization
version of MAML is claimed by the author to have worse performance than
original MAML. We would like to re-emphasize that our experiments were
conducted to validate our theories but not to achieve SOTA results.

Comparing experimental results for different train-validation split settings,
we note that the train loss at last epoch for $m_{va}=1$ is smaller than
$m_{va}=8$, while the best test accuracy is obtained with $m_{va}=8$. Non-
rigorously we think the generalization error of $m_{va}=8$ should be smaller
than $m_{va}=1$. The consistent result was verified by the gradient-
incoherence bound, which is the tightest for $m_{va}=8$. For $m_{va}=15$,
i.e., training with 1-shot data, both the test accuracy, train loss and the
estimated bound were the worst.

Table 4: Test Accuracy for Omniglot, train with 2000 epochs $5$-way Test
Accuracy
---
Algorithm |  $m_{va}=15$ |  $m_{va}=8$ |  $m_{va}=1$
MAML $0$-step |  20.7% |  20.13% |  20.26%
MAML $1$-step |  88.43% |  95.8% |  92.43%
MAML $4$-step |  90.77% |  96.97% |  96.14%
MAML $10$-step |  91.06% |  97.07% |  96.53%
Meta-SGLD $0$-step |  19.48% |  20.06% |  20.29%
Meta-SGLD $1$-step |  88.8% |  95.95% |  92.8%
Meta-SGLD $4$-step |  91.1% |  96.97% |  96.1%
Meta-SGLD $10$-step |  91.26% |  97.1% |  96.53%

Comparison with the observed generalization error

Similar to the synthetic setting, we calculated the observed generalization
error by evaluating the expected difference between the train loss and test
loss. And we list the results of Omniglot data under different train-
validation split setting in the following Table 5, 6 and 7:

Table 5: $m_{tr}=8,m_{va}=8$

epoch | 200 | 400 | 600 | 800 | 1000 | 1200 | 1400 | 1600 | 1800
---|---|---|---|---|---|---|---|---|---
Train-Test gap | 0.01896 | 0.00364 | 0.008821 | 0.01856 | 0.01366 | 0.0001578 | 0.04087 | 0.02269 | 0.01669
Lipschitz | 4.8159 | 6.8108 | 8.3415 | 9.6319 | 10.7688 | 11.7966 | 12.7418 | 13.6215 | 14.4478
G_norm | 0.1835 | 0.2765 | 0.3578 | 0.4292 | 0.4959 | 0.5557 | 0.6134 | 0.6679 | 0.7204
G_inco (Ours) | 0.109 | 0.1372 | 0.1617 | 0.1841 | 0.2057 | 0.2252 | 0.2444 | 0.2625 | 0.2798

Table 6: $m_{tr}=15,m_{va}=1$

epoch | 200 | 400 | 600 | 800 | 1000 | 1200 | 1400 | 1600 | 1800
---|---|---|---|---|---|---|---|---|---
Train-Test gap | 0.01508 | 0.02493 | 0.1099 | 0.07129 | 0.01425 | 0.07677 | 0.007417 | 0.04808 | 0.04199
Lipschitz | 9.3429 | 13.2129 | 16.1824 | 18.6858 | 20.8914 | 22.8854 | 24.719 | 26.4258 | 28.0287
G_norm | 0.4536 | 0.6265 | 0.8012 | 0.9641 | 1.115 | 1.265 | 1.409 | 1.55 | 1.688
G_inco (Ours) | 0.123 | 0.1572 | 0.2146 | 0.2787 | 0.3437 | 0.4154 | 0.4775 | 0.5275 | 0.5848

Table 7: $m_{tr}=1,m_{va}=15$

epoch | 200 | 400 | 600 | 800 | 1000 | 1200 | 1400 | 1600 | 1800
---|---|---|---|---|---|---|---|---|---
Train-Test gap | 0.0474 | 0.001597 | 0.02478 | 0.01946 | 0.02008 | 0.006832 | 0.05856 | 0.09882 | 0.0331
Lipschitz | 45.8866 | 64.8935 | 79.4779 | 91.7732 | 102.6056 | 112.3988 | 121.4046 | 129.7869 | 137.6598
G_norm | 0.9537 | 0.9639 | 0.9756 | 0.9861 | 0.9974 | 1.011 | 1.025 | 1.039 | 1.053
G_inco (Ours) | 0.9534 | 0.9619 | 0.971 | 0.9785 | 0.9863 | 0.9959 | 1.006 | 1.015 | 1.025

Where Train-Test gap is the observed generalization error, G_inco is the whole
gradient incoherence bound, i.e:
$\sqrt{\frac{\sigma^{2}(\epsilon_{U}+\epsilon_{W})}{nm_{va}}}$, G_norm is the
corresponding bound w.r.t. gradient norm.

##  Appendix E Experiment Details

Although we have described the detailed algorithm in the main paper to obtain
a data-dependent estimate bound, we offer a more structural pseudo-code in
section G. We used Monte Carlo simulations to estimate our generalization
error bound in Theorem 6.2. Recall the accumulated gradient incoherence for
meta learner and base learner are respectively denoted as:

$\epsilon_{U}=\sum_{t=1}^{T}\mathbb{E}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},W_{I_{t}},U^{t-1}}\frac{\eta_{t}\gamma_{t}\|\epsilon_{t}^{u}\|^{2}_{2}}{2},~{}~{}~{}~{}\epsilon_{W}=\sum_{t=1}^{T}\sum_{i=1}^{|I_{t}|}\sum_{k=1}^{K}\mathbb{E}_{{B^{\text{va}}_{i,t,k},B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1}}}\frac{\beta_{t,k}\gamma_{t,k}\|\epsilon_{t,i,k}^{w}\|^{2}_{2}}{2}\,.$

In our experiments, the two terms are separately estimated. Since we have

$\tilde{R}_{B^{\text{va}}_{I_{t}}}(U^{t-1})=\frac{1}{|I_{t}|}\sum_{i\in
I_{t}}R_{B^{\text{va}}_{i,t}}(W^{K}_{i,t})\,,$

$\epsilon_{t}^{u}=\nabla\tilde{R}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}}}(U^{t-1})-\nabla\tilde{R}_{B^{\text{tr}}_{I_{t}}}(U^{t-1})$
is related to the last inner step output $W^{K}_{i,t}$. To estimate
$\epsilon_{U}$, we conducted 10 times Monte Carlo simulations for the
corresponding inner path at each iteration $t$, the gradients are calculated
with back-propagation. For $\epsilon_{W}$, it’s much simpler, we just
conducted 10 times Monte Carlo simulations at each inner step, see more
details in the code. Our code is modified based on Long [48] and Amit [49].

###  E.1 Synthetic Data

Network Structure For Synthetic Data, the model structure is quite simple. It
is a 2D mean estimation. For a single task with parameter $w$, to estimate the
mean, we need to calculate the loss $\ell(W,Z)=||W-Z||_{2}^{2}$. Hence, we
constructed a single layer that conducts $W-Z$. Then the output of this layer
and the pseudo target (always set to 0) were taken as input to a square loss
function.

Hyper parameters | values
---|---
task numbers $n$ | 20000
sample numbers $m$ | 16
outer Loop inverse temperature $\gamma_{t}$ | 10000
Inner Loop inverse temperature $\gamma_{t,k}$ | 10000
Outer Loop learning rate $\eta_{t}$ | $0.2$
Inner Loop learning rate $\beta_{t,k}$ | $0.4$
task batch size $|I_{t}|$ | 5
epoch/Outer Loop iterations $T$ | 200
Inner Loop updates $K$ | 4
$m_{\text{va}}$ | $\\{1,8,15\\}$
$m_{\text{tr}}$ | $\\{15,8,1\\}$
data dimension | 2
loss | square loss
test update step | 10
Table 8:  Synthetic Data Experiment Setting

Training Details The hyper parameter settings and training details for
Synthetic data set are presented in Table 8.

Compute Resource All experiments for Synthetic data were tested on a machine
runing macOS system with an Intel Core i5 CPU, 8G memory.

Subgaussian parameter For the synthetic data, we want to estimate the mean for
each sub-task, where we have for task $i$,
$Z\sim{\mathcal{N}}(\mu_{i},0.1\mathbb{I}_{d}),d=2$. The task mean $\mu_{i}$
is sampled from the truncated normal distribution
${\mathcal{N}}((-4,-4)^{T},5\mathbb{I}_{2})$ with
$\mu_{i}\in[-12,4]\times[-12,4]$. Thus we have $||\mu_{i}||_{2}^{2}\leq 288$.
$\tilde{W}$ is the independent copy of the SGLD algorithm output $W$. To
estimated the $\sigma^{2}$ that satisfies the subgaussian loss, We consider
the worst case where the output is obtained with a single example $Z^{\prime}$
and one inner step update. So we have
$W=\textbf{0}-2\beta(\textbf{0}-Z^{\prime})+\epsilon\approx 0.8Z^{\prime}$,
since the inner loop learning rate in our experiment setting is $0.4$(the
noise added is quite small, which can be ignored). Hence,
$\tilde{W}\sim{\mathcal{N}}(0.8\mu_{i},0.064\mathbb{I}_{d})$. Moreover, we
have $\tilde{W}\perp\\!\\!\\!\perp Z$ and
$\ell(\tilde{W},Z)=||\tilde{W}-Z||_{2}^{2}$, so
$\tilde{W}-Z\sim{\mathcal{N}}(0.2\mu_{i},\sigma_{l}^{2}\mathbb{I}_{d}),\sigma_{l}^{2}=0.164$.
Furthermore,
$\ell(\tilde{W},Z)\sim\sigma_{l}^{2}\prime{\chi}_{d}^{2}(k),k=0.04||\mu_{i}||_{2}^{2}$,
which is a noncentral chi-squared distribution(Bu et al. [37] analyzed ERM,
where $\ell(\tilde{W},Z)$ follows central chi-squared distribution). Thus the
CGF of $\ell(\tilde{W},Z)$ is given by:

$\begin{aligned}
\psi_{\ell(\tilde{W},Z)}(\lambda)&=-(d+k)\sigma_{l}^{2}\lambda-\frac{d}{2}\log(1-2\sigma_{l}^{2}\lambda)+\frac{k\sigma_{l}^{2}\lambda}{1-2\sigma_{l}^{2}\lambda}\\\
&=\frac{d}{2}(-2\sigma_{l}^{2}\lambda-\log(1-2\sigma_{l}^{2}\lambda))+k\sigma_{l}^{2}\lambda\frac{2\sigma_{l}^{2}\lambda}{1-2\sigma_{l}^{2}\lambda},\lambda\in(-\infty,\frac{1}{2\sigma_{l}^{2}})\end{aligned}\,$

Let $u\overset{{\rm\mbox{\tiny def}}}{=}2\sigma_{l}^{2}\lambda$, and note that
$-u-\log(1-u)\leq\frac{u^{2}}{2},u<0$.

$\psi_{\ell(\tilde{W},Z)}(\lambda)=\frac{d}{2}(-u-\log(1-u))+\frac{ku^{2}}{2(1-u)}\leq\frac{du^{2}}{4}+\frac{ku^{2}}{2}=(2k+d)\sigma_{l}^{4}\lambda^{2},\lambda<0\,.$

So the subgaussian parameter $\sigma^{2}$ in our assumption can be expressed
as
$\sigma^{2}=2(2k+d)\sigma_{l}^{4}=2(2*0.04||\mu_{i}||_{2}^{2}+d)(0.164)^{2}$,
where $d=2$ and $||\mu_{i}||\leq 288$. So we obtain
$\sigma^{2}=0.164*0.164*4*(1+0.04*288)=1.3469$.

###  E.2 Omniglot

Network Structure We used a CNN network architecture for Omniglot data set,
which consists of a stack of modules. The first three modules are the same,
each of which is a $3\times 3$ 2d convolution layer of 64 filters and stride 2
followed by a Relu layer and a batch normalization layer. Then the fourth
module is a $2\times 2$ 2d convolution layer of 64 filters and stride 1,
followed by a Relu layer and a batch normalization layer. Through the
aforementioned modules, we got a $64\times 1\times 1$ feature map. This
feature map was further taken into a fully connected layer which output the
logits for a $5$-way classification. Finally, the cross-entropy loss is
calculated with the logits and the corresponding labels.

Training Details The hyper parameter settings and training details for
Omniglot data set are outlined in Table 9.

Compute Resource The experiments for Omniglot were run on a server node with 6
CPUs and 1 GPU of 32GB memory.

Subgaussian parameter For Omniglot data, we used the cross entropy loss, which
is unbounded. And the data distribution is too complex that we cannot obtain a
similar closed form estimation for the subgaussian parameter. To assure the
theoretic guarantee, we can adopt a variation of the loss function which is
clipped to $[0,2]$ and hence $1$-subgaussian. Actually, such clip is not
always necessary. As we discussed in section C, the subgaussian parameter
$\sigma^{2}$ is related to the independent copy $\tilde{W}$ of the base
learner output for each task. During our experiments, the loss w.r.t
$\tilde{W}$ rarely exceed the clip value.

Hyper parameters | values
---|---
task numbers $n$ | $\tbinom{1200}{5}$
sample numbers $m$ | 16
outer Loop inverse temperature $\gamma_{t}$ | 100000000
Inner Loop inverse temperature $\gamma_{t,k}$ | 100000000
Outer Loop learning rate $\eta_{t}$ | $10^{-3}*0.96^{\frac{t}{800}}$
Inner Loop learning rate $\beta_{t,k}$ | $0.3*0.96^{\frac{t}{1000}}$
n-way classification | 5
task batch size $|I_{t}|$ | 32
epoch/Outer Loop iterations $T$ | 2000
Inner Loop updates $K$ | 4
$m_{\text{va}}$ | $\\{1,8,15\\}$
$m_{\text{tr}}$ | $\\{15,8,1\\}$
loss | cross entropy
test update step | 10
image size | 28*28
image channel | 1
Table 9:  Omniglot Experiment Setting

##  Appendix F Additional Comparison to Related Works

Discussion with Jose and Simeone [20] They adopted different and generally
unrealistic assumptions to derive the theoretical results. Concretely:

In joint-training (Eq (33) in Jose and Simeone [20]), the task-level error
w.r.t. base-learner $W$ is related to the unknown environment distribution
$P_{T}$, which is hard to estimate from the observed data. In contrast, the
task-level risk in our paper is associated with the distribution meta-
parameter $U$, which can be evaluated efficiently. Besides, when $m\to\infty$
and the number of task $n$ is limited, their bound always has a non-zero term.
This does not fit the reality since the new task already has enough samples to
learn.

In the alternate-training (meta train-validation) settings, they assumed the
task parameters $W$ and $S^{va}$ are conditionally independent given $S^{tr}$
(Eq A(8) in their paper). This is an unrealistic condition in meta-learning
since $W$ depends on the meta-parameter $U$, where $U$ is updated by
$S^{va}_{1:n}$. As a result, if we set $m=1$ (each task has only one sample),
then $n\to\infty$, the upper bound in Eq(3) of [20] will converge to 0, which
is problematic since task distribution can be arbitrary noisy and the task-
level error (with one sample) can be quite large. Besides, this bound is
irrelevant to the train validation split, which is inconsistent with the
previous work such as [33, 35].

Therefore, our theoretical results are not directly comparable. Even if we
ignore all these unrealistic theoretical assumptions and directly compare the
results in Jose and Simeone [20], their theoretical results in noisy iterative
approaches still depend on the Lipschitz constant of the neural network (Eq
(45) in their paper), which is vacuous in deep learning.

Discussion with recent theoretical analysis on the support-query approach

Denevi et al. [33] first studied train-validation split for meta-learning in
biased linear regression model. 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. Specifically, they constructed two
datasets: For the simple unimodal distribution, the optimal split is
$m_{tr}=0$. For the bimodal distribution, the optimal split is
$m_{tr}\in(0,m-1]$.

Bai et al. [34] proposed a theoretical analysis of train-validation split in
linear centroid meta-learning (parameter transfer). By comparing the train-val
(alternate training) and train-train (joint training) method, they showed that
train-validation split is necessary for the agnostic setting, where the train-
val meta loss is an unbiased estimator w.r.t. the meta-test loss while the
train-train loss is biased(consistent with our Theorem 5.1). When it is
realizable (noiseless scenario), the train-train model can achieve better
excess loss.

Saunshi et al. [35] analyze the train-valid splitting for linear
representation learning (representation transfer). They proved that the train-
validation split encourages learning a low-rank representation. In the
noiseless setting, the train-val method already enables low-rank
representation, so it’s preferable to set a smaller train-split and larger
validation-split.

While our work focus on general settings with randomized algorithms and does
not specify the form of base-learner and meta-learner, which can be applied in
non-linear representation, non-linear classifier, and non-convex loss.
Besides, the relations of our papers are as follows:

1\. Our theory can recover the stochastic version of the above parameter and
representation transfer settings. If we consider the linear model with
$\mathcal{U}=\mathcal{W}\subseteq R^{d}$ and $P_{W|U}$ is approximated by a
Gaussian distribution $\mathcal{N}(U,\mathbb{I}_{d})$, the problem is
analogous to parameter-transfer meta-learning. If $\mathcal{U}\subseteq
R^{k},\mathcal{W}\subseteq R^{k+d}$ (where $U\in R^{k}$ is the shared
representation parameter, $V\in R^{d}$ is the parameter of the linear
classifier, $W=(U,V)\in R^{(k+d)}$ is the whole task parameter) and the prior
of stochastic linear classifier $V$ is approximated by a Gaussian distribution
$\mathcal{N}(0,\mathbb{I}_{d})$, the setting is similar to the representation
transfer paradigm.

2\. Since our bounds are based on the generic settings (flexible data
distribution, algorithm, and loss choice), the two training modes are not
directly comparable in our problem. However, we agree on the potential limit
of joint training (asymptotically biased in the agnostic setting) and believe
it is highly interesting to explore the specific conditions to understand the
benefits and limitations of these training modes as the future work.

##  Appendix G Pseudo Code

Require: Task environment $\tau$;

Require: initial learning rates $\eta_{0},\beta_{0}$, inverse temperature
$\gamma$;

randomly initialize $U^{0}$;

for  _$t\leftarrow 1$ to $T$_ do

Sample task data batch $B_{i}\sim\mu_{m,\tau},\forall i\in I_{t}$;

Randomly split $B_{I_{t}}$ to $B_{I_{t}}^{tr}$ and $B_{I_{t}}^{va}$;

learning rate decay, get $\eta_{t}$;

for  _$i\leftarrow 1$ to $|I_{t}|$_ do

for  _$k\leftarrow 1$ to $K$_ do

learning rate decay, get $\beta_{t,k}$;

if  _GLD_ then

Use full batch, $B_{i,t,k}^{tr}=B_{i,t}^{tr}$ and
$B_{i,t,k}^{tr}=B_{i,t}^{va}$;

else

Sample $B_{i,t,k}^{tr}$ from $B_{i,t}^{tr}$;

Sample $B_{i,t,k}^{va}$ from $B_{i,t}^{va}$;

end if

Update parameter with gradient descent:;

if  _$k==1$_ then

$W_{i,t}^{k-1}=U^{t-1}$;

end if

Calculate
$\mathbb{E}_{{B^{\text{va}}_{i,t,k},B^{\text{tr}}_{i,t,k},W_{i,t}^{k-1}}}\frac{\beta_{t}^{k}\gamma_{t}^{k}||\epsilon_{t,i,k}^{w}||^{2}_{2}}{2}$
with Monte Carlo simulation;

$W^{k}_{i,t}=W^{k-1}_{i,t}-\beta_{t,k}\nabla
R_{B^{\text{tr}}_{i,t,k}}(W^{k-1}_{i,t})+\zeta^{t,k}$;

end for

end for

Calculate
$\mathbb{E}_{B^{\text{va}}_{I_{t}},B^{\text{tr}}_{I_{t}},U^{t-1},W_{I_{t}}}\frac{\eta_{t}\gamma_{t}||\epsilon_{t}^{u}||^{2}_{2}}{2}$
with Monte Carlo Simulation;

$U^{t}=U^{t-1}-\eta_{t}\nabla\frac{1}{|I_{t}|}\sum_{i\in
I_{t}}R_{B^{\text{va}}_{i,t}}(W^{K}_{i,t})+\xi^{t}$

end for

Algorithm 1 Meta-SGLD for Few-Shot Learning