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

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 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 have gained tremendous success by exploiting the capabilities of deep neural networks . However, many theoretical questions still remain elusive. For instance, in the most popular methods for few-shot learning , 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 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 . Compared with previous theoretical results, the highlights of our contributions are as follows:

Unified Approach We analyze two popular scenarios. 1) The conventional LTL , 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 , 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 .

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, 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) for the Meta-SGLD algorithm, which is a stochastic variant of MAML that uses the Stochastic Gradient Langevin Dynamics (SGLD) . 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.

Related Work

Conventional LTL The early theoretic framework, introduced by Baxter , proposed the notion of task environment and derived uniform convergence bounds based on the capacity and covering numbers of function classes. Pentina and Lampert proposed PAC-Bayes risk bounds that depend on environment-level and task-level errors. Amit and Meir extended this approach and provided a tighter risk bound. However, their theory applies to stochastic neural networks and used factorized Gaussians to approximate the parameters’ distributions, which is computationally expensive to use in practice. Jose and Simeone 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 have drawn increasing attention since they are model-agnostic and are easily deployed for complex tasks like reinforcement learning, computer vision, and federate learning . Then, Reptile provided a general first-order gradient calculation method. Other methods combine MAML and Bayesian methods through structured variational inference and empirical Bayes . In Bayes MAML, 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. analyzed the average excess risk for Stochastic Gradient Descent (SGD) with Convex and Lipschitz loss. Balcan et al. studied meta-learning through the lens of online convex optimization, and has provided a guarantee with a regret bound. Khodak et al. 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. and Finn et al. . Finally, 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. 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. 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. 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 and Xu and Raginsky , 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 . Pensia et al. applied the mutual-information framework to a broad class of iterative algorithms, including SGLD and stochastic gradient Hamiltonian Monte Carlo (SGHMC). Negrea et al. provided data-dependent estimates of information-theoretic bounds for SGLD. For a recent comprehensive study, see Steinke and Zakynthinou .

Preliminaries

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:

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:

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

The corresponding conditional mutual information is defined as:

Information theoretic bound for single task learning

$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.

Problem Setup

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})$.

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, treated $U$ as the hyper-parameters of the base learner that produces $W$. In gradient based meta-learning such as MAML , $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}$.Although 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

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.

For Joint Training , 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:

For Alternate training, used in modern deep meta-learning algorithms , $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:

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

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.

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. , 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.

2 Conditional Mutual Information (CMI) Bound for Alternate Training

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})$

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.

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 , 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 . 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.

$\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.

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}\,.$

2 Bound for Alternate Training with Gradients Incoherence

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}$.

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}\,,$

Based on the nested loop structure and the independent sampling strategy, we have the following data-dependent generalization-error bound for Meta-SGLD.

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

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 , 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 . 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})$.

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

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 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).

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 . The Omniglot dataset contains 1623 characters for 50 different alphabets, and each character is present in 20 instances. We followed the experimental protocol of , 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.

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

Appendix A Technical Lemmas

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

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

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}$.

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

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

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

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

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

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

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

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

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

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

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

In contrast to previous works , 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.

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

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

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

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

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

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

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:

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 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 , 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. 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

In addition, the disintegrated mutual information is given as:

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

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

B.4 Proof of 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}\,.$

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:

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

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

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

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

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

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

B.5 Proof of 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

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.

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

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

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

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

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:

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

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:

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.

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

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

Appendix C On Subgaussianity

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

Xu and Raginsky 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 and section IV of . 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.

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

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

C.2 bounded loss

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

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.

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.

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 . We only trained the model with 2000 epochs, and the other hyper-parameter settings are also different from . Moreover, our Meta-SGLD code is modified based on . 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.

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:

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:

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

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.

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$.

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.

Appendix F Additional Comparison to Related Works

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

In joint-training (Eq (33) in Jose and Simeone ), 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 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 .

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 , 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. 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. 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. 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:

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