THEORETICAL BOUNDS ON ESTIMATION ERROR FOR META-LEARNING
Year: 2021

Abstract:
Machine learning models have traditionally been developed under the assumption that the training and test distributions match exactly. However, recent success in few-shot learning and related problems are encouraging signs that these models can be adapted to more realistic settings where train and test distributions differ. Unfortunately, there is severely limited theoretical support for these algorithms and little is known about the difficulty of these problems. In this work, we provide novel information-theoretic lower-bounds on minimax rates of convergence for algorithms that are trained on data from multiple sources and tested on novel data. Our bounds depend intuitively on the information shared between sources of data, and characterize the difficulty of learning in this setting for arbitrary algorithms. We demonstrate these bounds on a hierarchical Bayesian model of meta-learning, computing both upper and lower bounds on parameter estimation via maximum-a-posteriori inference.

heading: 1 INTRODUCTION
text: Many practical machine learning applications deal with distributional shift from training to testing. One example is few-shot classification (Ravi & Larochelle, 2016; Vinyals et al., 2016), where new classes need to be learned at test time based on only a few examples for each novel class. Recently, few-shot classification has seen increased success; however, theoretical properties of this problem remain poorly understood.
In this paper we analyze the meta-learning setting, where the learner is given access to samples from a set of meta-training distributions, or tasks. At test-time, the learner is exposed to only a small number of samples from some novel task. The meta-learner aims to uncover a useful inductive bias from the original samples, which allows them to learn a new task more efficiently.1 While some progress has been made towards understanding the generalization performance of specific meta-learning algorithms (Amit & Meir, 2017; Khodak et al., 2019; Bullins et al., 2019; Denevi et al., 2019; Cao et al., 2019), little is known about the difficulty of the meta-learning problem in general. Existing work has studied generalization upper-bounds for novel data distributions (Ben-David et al., 2010; Amit & Meir, 2017), yet to our knowledge, the inherent difficulty of these tasks relative to the i.i.d case has not been characterized.
In this work, we derive novel bounds for meta learners. We first present a general information theoretic lower bound, Theorem 1, that we use to derive bounds in particular settings. Using this result, we derive lower bounds in terms of the number of training tasks, data per training task, and data available in a novel target task. Additionally, we provide a specialized analysis for the case where the space of learning tasks is only partially observed, proving that infinite training tasks or data per training task are insufficient to achieve zero minimax risk (Corollary 2).
We then derive upper and lower bounds for a particular meta-learning setting. In recent work, Grant et al. (2018) recast the popular meta-learning algorithm MAML (Finn et al., 2017) in terms of inference in a Bayesian hierarchical model. Following this, we provide a theoretical analysis of a hierarchical Bayesian model for meta-linear-regression. We compute sample complexity bounds for posterior inference under Empirical Bayes (Robbins, 1956) in this model and compare them to our predicted lower-bounds in the minimax framework. Furthermore, through asymptotic analysis of the error rate of the MAP estimator, we identify crucial features of the meta-learning environment which are necessary for novel task generalization.
1Note that this definition encompasses few-shot learning.
Our primary contributions can be summarized as follows:
• We introduce novel lower bounds on minimax risk of parameter estimation in meta-learning. • Through these bounds, we compare the relative utility of samples from meta-training tasks
and the novel task and emphasize the importance of the relationship between the tasks.
• We provide novel upper bounds on the error rate for estimation in a hierarchical meta-linearregression problem, which we verify through an empirical evaluation.

heading: 2 RELATED WORK
text: An early version of this work (Lucas et al., 2019) presented a restricted version of Theorem 1. The current version includes significantly more content, including more general lower bounds and corresponding upper bounds in a hierarchical Bayesian model of meta-learning (Section 5).
Baxter (2000) introduced a formulation for inductive bias learning where the learner is embedded in an environment of multiple tasks. The learner must find a hypothesis space which enables good generalization on average tasks within the environment, using finite samples. In our setting, the learner is not explicitly tasked with finding a reduced hypothesis space but instead learns using a general two-stage approach, which matches the standard meta-learning paradigm (Vilalta & Drissi, 2002). In the first stage an inductive bias is extracted from the data, and in the second stage the learner estimates using data from a novel task distribution. Further, we focus on bounding minimax risk of meta learners. Under minimax risk, an optimal learner achieves minimum error on the hardest learning problem in the environment. While average case risk of meta learners is more commonly studied, recent work has turned attention towards the minimax setting (Kpotufe & Martinet, 2018; Hanneke & Kpotufe, 2019; 2020; Mousavi Kalan et al., 2020; Mehta et al., 2012). The worst-case error in meta-learning is particularly important in safety-critical systems, for example in medical diagnosis.
Mousavi Kalan et al. (2020) study the minimax risk of transfer learning. In their setting, the learner is provided with a large amount of data from a single source task and is tasked with generalizing to a target task with a limited amount of data. They assume relatedness between tasks by imposing closeness in parameter-space (whereas in our setting, we assume closeness in distribution via KL divergence). They prove only lower bounds, but notably generalize beyond the linear setting towards single layer neural networks.
There is a large volume of prior work studying upper-bounds on generalization error in multi-task environments (Ben-David & Borbely, 2008; Ben-David et al., 2010; Pentina & Lampert, 2014; Amit & Meir, 2017; Mehta et al., 2012). While the approaches in these works vary, one common factor is the need to characterize task-relatedness. Broadly, these approaches either assume a shared distribution for sampling tasks (Baxter, 2000; Pentina & Lampert, 2014; Amit & Meir, 2017), or a measure of distance between distributions (Ben-David & Borbely, 2008; Ben-David et al., 2010; Mohri & Medina, 2012). Our lower-bounds utilize a weak form of task relatedness, assuming that the environment contains a finite set that is suitably separated in parameter space but close in KL divergence—this set of assumptions also arises often when computing i.i.d minimax lower bounds (Loh, 2017).
One practical approach to meta-learning is learning a linear mapping on top of a learned feature space. Prototypical Networks (Snell et al., 2017) effectively learn a discriminative embedding function and performs linear classification on top using the novel task data. Analyzing these approaches is challenging due to metric-learning inspired objectives (that require non-i.i.d sampling) and the simultaneous learning of feature mappings and top-level linear functions. Though some progress has been made (Jin et al., 2009; Saunshi et al., 2019; Wang et al., 2019; Du et al., 2020). Maurer (2009), for example, explores linear models fitted over a shared linear feature map in a Hilbert space. Our results can be applied in these settings if a suitable packing of the representation space is defined.
Other approaches to meta-learning aim to parameterize learning algorithms themselves. Traditionally, this has been achieved by hyper-parameter tuning (Rasmussen & Nickisch, 2010; MacKay et al., 2019) but recent fully parameterized optimizers also show promising performance in deep neural network optimization (Andrychowicz et al., 2016), few-shot learning (Ravi & Larochelle, 2016), unsupervised learning (Metz et al., 2019), and reinforcement learning (Duan et al., 2016). Yet another
approach learns the initialization of task-specific parameters, that are further adapted through regular gradient descent. Model-Agnostic Meta-Learning (Finn et al., 2017), or MAML, augments the global parameters with a meta-initialization of the weight parameters. Grant et al. (2018) recast MAML in terms of inference in a Bayesian hierarchical model. In Section 5, we consider learning in a hierarchical environment of linear models and provide both lower and upper bounds on the error of estimating the parameters of a novel linear regression problem.
Lower bounding estimation error is a critical component of understanding learning problems (and algorithms). Accordingly, there is a large body of literature producing such lower bounds (Khas’ minskii, 1979; Yang & Barron, 1999; Loh, 2017). We focus on producing lower-bounds for parameter estimation using local packing sets, but expect that extending these results to density estimation or non-parametric estimation is feasible.

heading: 3 NOVEL TASK ENVIRONMENT RISK
text: Most existing theoretical work studying out-of-distribution generalization focuses on providing upper-bounds on generalization performance (Ben-David et al., 2010; Pentina & Lampert, 2014; Amit & Meir, 2017). We begin by instead exploring the converse: what is the best performance we can hope to achieve on any given task in the environment? After introducing notation and minimax risks, we then show how these ideas can be applied, using meta linear regression as an example.
A full reference table for notation can be found in Appendix A and a short summary is given here. We consider algorithms that learn in an environment (Z,P), with data domain Z = X × Y and P a space of distributions with support Z . In the typical i.i.d setting, the algorithm is provided training data S ∈ Zk, consisting of k i.i.d samples from P ∈ P . In the standard multi-task setting, we sample training data from a set of training tasks {P1, . . . , PM+1} ⊂ P . We extend this to a meta-learning, or novel-task setting by first drawing S1:M : n training data points from the first M distributions, for a total of nM samples. We call this the meta-training set. We then draw a small sample of novel data, called a support set, SM+1 ∈ Zk, from PM+1. Consider a symmetric loss function `(a, b) = ψ(ρ(a, b)) for non-decreasing ψ and arbitrary metric ρ. We seek to estimate the output of θ : P → Ω, a functional that maps distributions to a metric space Ω. For example, θ(P ) may describe the coefficient vector of a high-dimensional hyperplane when P is a space of linear models, and ρ may be the Euclidean distance.
The i.i.d minimax risk Before studying the meta-learning setting, we first begin with a definition of the i.i.d minimax risk that measures the worst-case error of the best possible estimator,
R∗ = inf θ̂ sup P∈P
ES∼Pk [ `(θ̂(S), θP ) ] . (1)
For notational convenience, we denote the output of θ(P ) by θP . The estimator for θ is denoted, θ̂ : Zk → Ω, and maps k samples from P to an estimate of θP .
Novel-task minimax risk In the novel-task setting, we wish to estimate θPM+1 , the parameters of the novel task distribution PM+1. We consider two-stage estimators for θPM+1 . In the first stage, the meta-learner uses a learning algorithm f : S1:M 7→ θ̂S1:M , that maps the meta-training set to an estimation algorithm, θ̂S1:M : Zk → Ω. In the second stage, the learner computes θ̂S1:M (SM+1), the estimate of θPM+1 .
The novel-task minimax risk is given by,
R∗P(β) = inf f
sup P1,...,PM+1∈QβP E S1:M∼Pn1:M SM+1∼PkM+1
[ ` ( (f(S1:M ))(SM+1), θPM+1 )] , (2)
where QβP = {(P1, . . . , PM+1) ∈ P : DKL (PM+1‖Pi) ≤ β, for i = 1, . . . ,M}. This ensures a degree of relatedness between the novel and meta-training tasks.
The estimator for θM+1 now depends additionally on theMn samples in S1:M , where only k Mn samples from PM+1 are available to the learner. Thus, R∗P addresses the domain shift expected at
test-time in the meta-learning setting and allows the learner to use data from multiple tasks. The goal of f is to learn an inductive bias from S1:M such that a good estimate is possible with only k data points from PM+1. In this setting, k is equivalent to the number of shots in few-shot learning.
An example with meta-linear regression We present here a short summary based on meta linear regression, which we will analyze in more detail in Section 5.
In Figure 1, we show observed data samples from a family of polynomial regression models. Our aim is to output an algorithm which recovers the parameters of a new polynomial function from limited observations–we choose a MAP estimator which is described fully in Section 5. In the bottom right, we are given only 5 data points from a novel task distribution and estimate the parameters of the model with both the MLE and MAP estimators — the MLE overfits the support set while the MAP estimator is close to the true function.
In terms of the terminology used above, the set,
P = {pθ(y) = N (x>θ, σ2) : θ ∈ Rd,x = [1, x, . . . , xd−1]},
is the space of polynomial regression models, parameterized by θ. For this problem, we take `(θ̂, θ) = ‖θ̂ − θ‖22. In Figure 1, tasks are generated with p(θ) = N (τ, σ2θ), for unknown, sparse, τ ∈ Rd. Thus, each model is a polynomial function with few large coefficients. The algorithm f , first takes samples from P1, P2, P3 and computes an estimate, τ̂ . This estimate of τ is then used to compute θ̂(SM+1; τ̂) = argmaxθ4 p(θ4|τ̂ , SM+1). Note that this approach is able to learn the correct inductive bias from the data, without requiring a carefully designed regularizer. The lower bounds we derive in Section 4 can be applied to problems of this general type, and the upper and lower bounds in Section 5 apply specifically to meta-learning linear regression.

heading: 4 INFORMATION THEORETIC LOWER BOUNDS ON NOVEL TASK GENERALIZATION
text: In this section, we first present our most general result: Theorem 1. Using this, we derive Corollary 1 that gives a lower bound in terms of the sample size in the training and novel tasks. Corollary 1 recovers a well-known i.i.d lower bound (Theorem 2) when Mn = 0, and, importantly, highlights that the novel task data is significantly more valuable than the training task data. Additionally, we provide a specialized bound that applies when the environment is partially observed — proving that in this setting training task data is insufficient to drive the minimax risk to zero.
In Theorem 1, we assume that P contains J distinct 2δ-separated distributions but only M + 1 ≤ J tasks are visible to the learner. Intuitively, the error rate lower-bound shrinks as the amount of information shared between the training tasks and the novel task grows. All proofs are given in Appendix B.1. Recall `(a, b) = ψ(ρ(a, b)) for non-decreasing ψ and arbitrary metric ρ. Theorem 1 (Minimax novel task risk lower bound). Let J ⊂ P contain J distinct distributions such that ρ(θP , θP ′) ≥ 2δ and DKL (P‖P ′) ≤ β for all P, P ′ ∈ J . Let π be a random ordering of the J elements, and Z|π be a vector of k i.i.d samples from PπM+1 . Further, define W |π to be an n×M matrix whose jth column consist of n i.i.d samples from Pπj . Then,
R∗P(β) ≥ ψ(δ) (
1− I(πM+1;W ) + I(πM+1;Z) + 1 log2 J
) .
Note that δ is a property of the so-called packing set, J , and may depend on the sample size, β, and other properties of P . For example, practical instances of this bound typically require ψ(δ) = O(1/k) or similar, as in Theorem 3 below. To derive this result, we bound the statistical estimation error by the error on a corresponding decoding problem where we must predict the novel task index, given the meta-training set S1:M and SM+1. Fano’s inequality provides best-case error rates for this problem.
Using Theorem 1, we derive our first bound on the novel-task minimax risk that depends on the number of meta-training tasks (M ) and datapoints per training task (n, k), via a local-packing argument. The following corollary implies that if we have J meta-training tasks in our 2δ-packing that are close (in terms of their pairwise KL distance), then learning a novel task from training samples drawn from the meta-training tasks requires significantly more examples; in particular, learning the novel task from samples drawn from the meta training set requires Ω(J) times the sample complexity of the novel task. This matches our intuition that learning the novel task implies the ability to distinguish it from all J well-separated meta-training tasks. Corollary 1. Assume the same setting as in Theorem 1. Then,
R∗P(β) ≥ ψ(δ)
1− 1 + ( Mn (J−1) + k ) 1 J2 ∑ 1≤i,j≤J DKL (Pi‖Pj)
log2 J  . A tighter bound on partially observed environments We now consider the special case of Theorem 1 when M < J − 1, meaning that the meta-training tasks cannot cover the full packing set. In this setting, we prove that no algorithm can generalize perfectly to tasks in unseen regions of the space with small k, regardless of the number of data points n observed in each meta-training task. Corollary 2. Assume the same setting as in Theorem 1, with M + 1 < J . Then,
R∗P ≥ ψ(δ)
( log2(J −M)− kJ2 ∑ 1≤i,j≤J DKL (Pi‖Pj)− 1
log2 J
) .
In this work, we have focused on the setting where W contains an equal number of samples from each of the meta-training tasks — this is the sampling scheme shown in Figure 2. However, it is possible to extend these results to different sampling schemes for W . For example, in the appendix we derive bounds with W |π as a mixture distribution. Surprisingly, despite task identity being hidden from the learner, the asymptotic rate for these two sampling schemes match.

heading: 4.1 MEASURING TASK-RELATEDNESS
text: The use of local packing requires the design of an appropriate set of distributions whose corresponding parameters are 2δ-separated but maintain small KL divergences. In the multi-task setting such an assumption is intuitively reasonable: challenging tasks should require separated parameters for ideal explanations (2δ-separated) but should satisfy some relatedness measure (small KL). Importantly, these parameters can depend on sample size and other problem-specific variables. As we will see shortly, lower bounds on minimax risk in the i.i.d setting may also assume the same notion of relatedness for the local-packing in P . Task relatedness is a necessary feature for upper-bounds on novel task generalization, but are typically difficult to define (see e.g. Ben-David & Borbely (2008)). Our lower bounds utilize a
relatively weak notion of task-relatedness, and thus may be overly pessimistic compared to the upper bounds computed in existing work. However, task relatedness of this form can be formulated in a representation space shared across tasks and thus can be applied in settings like those explored by e.g. Du et al. (2020). Deriving lower bounds under the different task relatedness assumptions present in the literature would make for exciting future work.
4.2 COMPARISON TO RISK OF i.i.d LEARNERS
From the statement of Theorem 1 it is not clear how this lower-bound compares to that of the i.i.d learner which has access only to the k samples from SM+1. To investigate the benefit of additional meta-training tasks, we compare our derived minimax risk lower bounds to those achieved by i.i.d learners. To do so, we revisit standard minimax lower bounds that can be found in e.g. Loh (2017).
Theorem 2 (IID minimax lower-bound). Suppose {P1, . . . , PJ} ⊆ P satisfy ρ(θPi , θPj ) ≥ 2δ for all i 6= j. Then,
R∗ ≥ ψ(δ) ( 1− k J2 ∑ 1≤i,j≤J DKL (Pi‖Pj) + 1
log2 J
) .
We include a proof of this result in Appendix B.1, using local-packing as in our meta-learning bounds. As hoped, Corollary 1 recovers Theorem 2 when there are no training tasks available. Moreover, this i.i.d bound is strictly larger than the one computed in Corollary 1 in general. Note that while this i.i.d minimax risk is asymptotically tight for several learning problems (Loh, 2017; Raskutti et al., 2011), there is no immediate guarantee that the same is true for our meta-learning minimax bounds. We investigate the quality of these bounds by providing comparable upper bounds in the next section.

heading: 5 ANALYSIS OF A HIERARCHICAL BAYESIAN MODEL OF META-LEARNING
text: Our goal is to analyze the sample complexity of meta-learning for linear regression, where samples are drawn from multiple meta-training tasks and we want to generalize to a new task with only a few data points. After introducing the setting, we will compute lower-bounds on the minimax risk using our results from Section 4, revealing a 2d scaling on the meta-training sample complexity. Following the lower bound, we derive an accompanying upper-bound on the risk of a MAP estimator, derived from an empirical Bayes estimate over a hierarchical Bayesian model. Asymptotic analysis of this bound reveals that if the observed samples from the novel task vary considerably more than the task parameters, then observing more meta-training samples may significantly improve convergence in the small k regime. This is validated empirically in Section 6.
For i = 1...M + 1, where M + 1 is the total number of tasks, we define,
yi = Xiθi + i, Xi ∈ Rni×d,yi ∈ Rni , i ∈ Rni
i ∼ N (0, σ2i I), σ2i ∈ R+
Each task has some design matrix Xi and unknown parameters θi. For simplicity, we assume known isotropic noise models and that ni = n for all i ≤M , with nM+1 = k. Our meta learner will fit the data using an empirical Bayes estimate in a hierarchical Bayesian model:
θi = τ + ξ, τ ∈ Rd, ξ ∈ Rd, ξ ∼ N (0, σ2θI), σ2θ ∈ R+
We will consider the Maximum a Posterior estimator,
θ̂M+1 = argmax θM+1 p(θM+1|y1, . . . ,yM+1),
and will characterize its risk, E[‖θ̂M+1 − θM+1‖22], where the expectation is with respect to sampled data only. The posterior distribution under the Empirical Bayes estimate for τ is given in Appendix C.2. The derivation is standard but dense and we recommend dedicated readers to consult Gelman et al. (2013), or an equivalent text, for more details.

heading: 5.1 MINIMAX LOWER BOUNDS
text: We now compute lower bounds for parameter estimation with meta-learning over multiple linear regression tasks. Beginning with a definition of the space of data generating distributions,
PLR = {pθ(y) = N (Xθ, σ2I) : θ ∈ B2(1), X ∈ Rn×d.}
where θ are the parameters to be learned, and X is the design matrix of each linear regression task in the environment. We write γ = maxi σmax(Xi/ √ n), which we assume is bounded for all X and n (an assumption that is validated for random Gaussian matrices by Raskutti et al. (2011)). Theorem 3 (Meta linear regression lower bound). Consider PLR defined as above and let `(a, b) = (‖a− b‖2)2. If d ≥ 2 and 2−dM + kn−1 ≥ max{ d4β , dσ 2/(256γ2n), then,
R∗PLR(β) ≥ O (
dσ2
γ2(2−dnM + k) ) The proof is given in Appendix B.5. We see that the size of the meta-training set has an inverse exponential scaling in the dimension, d. This reflects the complexity of the space growing exponentially in dimensions and the need for a matching growth in data size to cover the environment sufficiently.

heading: 5.2 MINIMAX UPPER BOUNDS
text: To compute upper bounds on the estimation error, we require an additional assumption. Namely, we will assume that the design matrices also have bounded minimum singular values, 0 < s ≤ σmin(X/ √ n) (see Raskutti et al. (2011) for some justification). For the upper-bounds, we allow the bounds on the singular values of the design matrices and the observation noise in the novel task to be different than those in the meta-training tasks. We note that we can still recover the setting assumed in the lower bounds, where all tasks match on these parameters, as a special case.
The learner observes n data points from each linear regression model in {Pθ1 , . . . , PθM } ⊂ P . We then bound the error of estimating θM+1, for which k samples are available.
The expected error rate of the MAP estimator can be decomposed as the posterior variance and bias squared. In the appendix we provide a detailed derivation of these results. The bound depends on dimensionality d, the observation noise in each task σ2i , the number of tasks M , the number of data points in each meta-training task n, and the number of data points in the novel task k.
Theorem 4 (Meta Linear Regression Upper Bound). Let θ̂M+1 be the maximum-a-posteriori estimator, µθM+1|Y1:M+1 . Then,
R∗PLR ≤ sup θ1,...,θM+1∈B2(1)
E[‖θ̂M+1 − θM+1‖2] ≤ O ( dσ2M+1C(M,n, k) −2D(M,n, k) )
where,
C(M,n, k) = k + Mn n(M+κ2)s22
α2 +A
 , and, D(M,n, k) = [k + Mn ( nL1 +A1)( Mn L2 +A2) ] .
Expectations are taken over the data conditioned on θ1, . . . ,θM+1. Additional terms not depending on d, M, n, k are defined in Appendix C.2.
While the bounds presented in Theorem 4 are relatively complicated, we can probe the asymptotic convergence of the MAP estimator to the true task parameters, θM+1. In the following section, we will discuss some of the consequences of this result and its implications for our lower bounds.

heading: 5.3 ASYMPTOTIC BEHAVIOR OF THE MAP ESTIMATOR
text: We first notice that when k is small, the risk cannot be reduced to zero by adding more meta-training data. Recent work has suggested such a relationship may be inevitable (Hanneke & Kpotufe, 2020). Our lower bound presented in Corollary 2 agrees that more samples from a small number of metatraining tasks will not reduce the error to zero. However, unlike our lower bounds based on local
packing, the lower bounds presented in this section predict that if the meta-training tasks cover the space sufficiently then an optimal algorithm might hope to reduce the error entirely with enough samples. We hypothesize that this gap is due to limitations in the standard proof techniques we utilize for the lower-bounds when the number of tasks grows, and expect a sharper bound may be possible.
To emulate the few-shot learning setting where k is relatively small, we consider n→∞, with k and M fixed. In this case, the risk is bounded as,
sup θ1,...,θM+1∈B2(1)
E[‖θ̂M+1 − θM+1‖2] ≤ O ( dσ2M+1 [ k + 2α2M
M + κ2
]−1) ,
where α2 = σ2M+1/σ 2 θ , is the ratio of the observation noise to the variance in sampling θ, and κ is the condition number of the design matrices. This leads to a key takeaway: if the observed samples from PM+1 vary considerably more than the parameters θ, then observing more samples in S1:M will significantly improve convergence towards the true parameters in the small k regime. Further, adding more tasks (increasing M ) also improves these constant factors by removing the dependence on the condition number, κ.

heading: 6 EMPIRICAL INVESTIGATIONS
text: In this section, we provide additional quantitative exploration of the upper bound studied in Section 5. The aim is to take steps towards relating the bounds to experimental results; we know of little theoretical work in meta-learning that attempt to relate their results to practical empirical datasets. Full details of the experiments in this section can be found in Appendix D.

heading: 6.1 HIERARCHICAL BAYES POLYNOMIAL REGRESSION
text: We first focus on the setting of polynomial regression over inputs in the range [−1, 1]. Some examples of these functions and samples are presented in Figure 1, alongside the MAP and MLE estimates for the novel task.
Figure 2 shows the analytical expected error rate (risk) under various environment settings. We observe that even in this simple hierarchical model, the estimator exhibits complex behavior that is correctly predicted by Theorem 4. In Figure 2A, we varied the novel task difficulty by increasing the novel task observation noise (σ2M+1). We plot three curves for three different dataset size configurations. When the novel task is much noisier than the source tasks, it is greatly beneficial to add more meta-training data (blue vs. red). And while larger k made little difference when the novel task was relatively difficult (blue vs. green), the expected loss was orders of magnitude lower when the novel task became easier. In Figure 2B, we fixed the relative task difficulty and instead varied k and M . The x-axis now indicates the total data Mn+ k available to the learner. We observed that adding more tasks has a large effect in the low-data regime but, as predicted, the error has a non-zero asymptotic lower-bound — eventually it is more beneficial to add more novel-task data samples.
These empirical simulations verify that our theoretical analysis is predictive of the behavior of this meta learning algorithm, as each of these observations can be inferred from Theorem 4. While this model is simple, it captures key features of and provides insight into the more general meta-learning problem. We also explored a non-linear sinusoid meta-regression problem (Finn et al., 2017), finding that our theory is largely predictive of the general trends in this setting too.

heading: 6.2 SINUSOID REGRESSION WITH MAML
text: Following the connections between MAML and hierarchical Bayes explored by Grant et al. (2018), we also explored regression on sinusoids using MAML. Our aim was to investigate how predictive our linear theory is for this highly non-linear problem setting. As in Finn et al. (2017), we sample sinusoid functions by placing a prior over the amplitude and phase. In other works (Finn et al., 2017; Grant et al., 2018) the same prior is used for the training and testing stages. However, to better measure generalization to novel tasks we use different prior distributions when training versus evaluating the model.
We display the risk averaged over 30 trials in Figure 3. We varied the novel task difficulty by increasing the observation noise in the novel task. We plot separate curves for different dataset size configurations, and observe that the empirical results align fairly well with the results derived by sampling the hierarchical model (Figure 2A). Adding more meta-training data (increasing n) is beneficial (green vs. yellow) and adding more test data-points (higher k) is also beneficial (red vs. green). Here however, these relationships did not interact with the task difficulty, as the wins for increased meta-training and meta-testing data were consistent, until task noise prevents any setting of the model from performing the task.

heading: 7 CONCLUSION
text: Meta-learning algorithms identify the inductive bias from source tasks and make models more adaptive towards unseen novel distribution. In this paper, we take initial steps towards characterizing the difficulty of meta-learning and understanding how these limitations present in practice. We have derived both lower bounds and upper bounds on the error of meta-learners, which are particularly relevant in the few-shot learning setting where k is small. Our bounds capture key features of the meta-learning problem, such as the effect of increasing the number of shots or training tasks. We have also identified a gap between our lower and upper bounds when there are a large number of training tasks, which we hypothesize is a limitation of the proof technique that we applied to derive the lower bounds — suggesting an exciting direction for future research.

heading: 8 ACKNOWLEDGEMENTS
text: This work benefited greatly from the input of many other researchers. In particular, we extend our thanks to Shai Ben-David, Karolina Dziugaite, Samory Kpotufe, and Daniel Roy for discussions and feedback on the results presented in this work. We thank Ahmad Beirami and anonymous reviewers for their valuable feedback that led to significant improvements to this paper. We also thank Elliot Creager, Will Grathwohl, Mufan Li, and many of our other colleagues at the Vector Institute for feedback that greatly improved the presentation of this work. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute (www.vectorinstitute.ai/partners).

heading: B LOWER BOUND PROOFS
text: We will make use of several standard results below, which we present here.
Lemma 1. Fano’s Inequality (Fano, 1961; Cover & Thomas, 2012) For any estimator Ŷ of a random variable Y such that Y → Z → Ŷ forms a Markov chain, it holds that,
P(Ŷ 6= Y ) ≥ H(Y |Z)− 1 log2 |Y | = H(Y )− I(Y ;Z)− 1 log2 |Y | .
Lemma 2. Mutual information equality (Khas’ minskii, 1979) Consider random variables Z1, Z2, Y , then,
I(Y ; (Z1, Z2)) + I(Z1;Z2) = I(Z1; (Z2, Y )) + I(Z2;Y )
Lemma 3. Local packing lemma (Loh, 2017) Consider distributions P1, . . . , PJ ∈ P . Let Y be a random variable distributed uniformly on [J ] and let Z|{Y = j} be a vector of k i.i.d samples from
Pj . Then,
I(Y ;Z) ≤ k J2 ∑ 1≤i,j≤J DKL (Pi‖Pj) .
We will require a novel local packing bound for the novel-task risk, which we present in Lemma 5.
B.1 IID LOWER BOUND
We first prove the i.i.d result, which will serve as a guide for our novel lower bounds. Theorem 2 (IID minimax lower-bound). Suppose {P1, . . . , PJ} ⊆ P satisfy ρ(θPi , θPj ) ≥ 2δ for all i 6= j. Then,
R∗ ≥ ψ(δ) ( 1− k J2 ∑ 1≤i,j≤J DKL (Pi‖Pj) + 1
log2 J
) .
Proof. First, notice that,
sup P∈P
ES∼Pk [ `(θ̂(S), θP ) ] ≥ 1 J J∑ i=1 ES∼Pki [ `(θ̂(S), θPi) ] .
Now define the decision rule, f(S) = argmin
1≤j≤J ρ(θ̂(S), θPj )],
with ties broken arbitrarily. We proceed by bounding the expected loss. First, using Markov’s inequality,
ES∼Pki [ `(θ̂(S), θPi) ] ≥ ψ(δ)PS∼Pki [ ψ(ρ(θ̂(S), θPi)) ≥ ψ(δ) ] ,
= ψ(δ)PS∼Pki [ ρ(θ̂(S), θPi) ≥ δ ] .
Next, consider the case ρ(θ̂(S), θi)) < δ. Through the triangle inequality,
ρ(θ̂(S), θPj ) ≥ ρ(θPi , θPj )− ρ(θ̂(S), θPi) ≥ 2δ − δ > ρ(θ̂(S), θPi)
Thus, the probability that the distance is less than δ is at least as large as the probability that the estimator is correct.
ψ(δ)PS∼Pki [ `(θ̂(S), θPi) ≥ ψ(δ) ] ≥ ψ(δ)P(f(S) 6= i).
Now, using Fano’s inequality with Y = πM+1, and Ŷ = f(S) (and the corresponding Markov chain πM+1 → S → f(S)), we have,
1
J J∑ i=1 P(f(S) 6= i) ≥ log2 J − I(πM+1;Z)− 1 log2 J .
Combining the above inequalities with the Local Packing Lemma gives the final result.

heading: B.2 PROOF OF THEOREM 1
text: Theorem 1 (Minimax novel task risk lower bound). Let J ⊂ P contain J distinct distributions such that ρ(θP , θP ′) ≥ 2δ and DKL (P‖P ′) ≤ β for all P, P ′ ∈ J . Let π be a random ordering of the J elements, and Z|π be a vector of k i.i.d samples from PπM+1 . Further, define W |π to be an n×M matrix whose jth column consist of n i.i.d samples from Pπj . Then,
R∗P(β) ≥ ψ(δ) (
1− I(πM+1;W ) + I(πM+1;Z) + 1 log2 J
) .
Proof. As in the i.i.d case, we first bound the supremum from below with an average,
sup P ′1,...,P ′ M+1∈P ES1:M∼(P ′1:M )n SM+1∼(P ′i ) k
[ `(θ̂S1:M (SM+1), θ(P ′i )) ] ≥ 1 J J∑ i=1 1( J−1 M ) ∑ π|{πM+1=i} Ew∼W |π z∼Z|π [ `(θ̂w(z), θi) ] ,
where the inner sum is over all length M orderings, π with πM+1 = i.
As before, we consider the following estimator,
f(W,Z) = argmin 1≤j≤J ρ(θ̂W (Z), θ(Pj))
Using Markov’s inequality, and then following the proof of Theorem 2, we have,
1
J J∑ i=1 1( J−1 M ) ∑ π|{πM+1=i} Ew∼W |π z∼Z|π [ `(θ̂w(z), θi) ] ≥ 1 J J∑ i=1 1( J−1 M ) ∑ π|{πM+1=i} ψ(δ)P[f(W,Z) 6= i|π]
= ψ(δ)P[f(W,Z) 6= πM+1]
with the use of Fano’s inequality, we arrive at,
ψ(δ) ( 1− I(πM+1; (W,Z)) + 1
log2 J ) Conditioned on Y , each element of W and Z are independent but they are not identically distributed. Thus, with the application of Lemma 2,
I(πM+1; (W,Z)) ≤ I(πM+1;Z) + I(πM+1;W )
The result follows by combining these inequalities.
Remark In the above proof of Theorem 1, we did not need to make use of the form of the distribution of W |Y = i, only that the correct graph structure was observed. This grants us some flexibility, which we utilize later in Section B.4 to prove lower bounds for mixture distributions.
We now proceed with proofs of the corollaries of Section 4.

heading: B.3 LOCAL PACKING RESULTS
text: Lemma 4 (Meta-learning local packing). Consider the same setting as in Theorem 1, then
I(πM+1;W ) ≤ Mn J2(J − 1) ∑
1≤i,j≤J
DKL (Pi‖Pj)
Proof. There are (J − 1)!/(J −M − 1)! orderings on the first M indices, given the (M + 1)th. We introduce the following notation,
P̄−i := (J −M − 1)! (J − 1)! ∑
π|πM+1=i
p(W |π) P̄ := 1 J J∑ i=1 P̄−i
As in previous proofs, we notice that we can write,
P̄ = 1
J P̄−i + J − 1 J 1 J − 1 ∑ j 6=i P̄−j
First, note that we can upper bound I(πM+1;W ) ≤ nI(πM+1;w), where w denotes a single row in W . Further,
I(πM+1;w) = 1
J J∑ i=1 E log P̄−i P̄
= 1
J J∑ i=1 DKL P̄−i‖ 1 J P̄−i + J − 1 J 1 J − 1 ∑ j 6=i P̄−j  ≤ 1 J J∑ i=1 1 J DKL ( P̄−i‖P̄−i ) + J − 1 J DKL P̄−i‖ 1 J − 1 ∑ j 6=i P̄−j
 ≤ 1 J(J − 1) ∑ 1≤i 6=j≤J DKL ( P̄−i‖P̄−j
) We will use convexity of the KL divergence to upper bound this quantity. Each distribution P̄−i is an average over a random selection of index orderings.
When applying convexity, all pairs of selections that exactly match will lead to a KL divergence of zero. There are the same number of these in each component of P̄−i. Thus we care only about selections that contain either j or i such that matching pairs of distributions exactly is not possible. Further, we need only consider pairs of product distributions who differ only in a single, identical position.
Each of the above described pairs of distributions has KL divergence equal to DKL (Pj‖Pi). We conclude by counting the total number of orderings producing such pairs. First, there are M choices for the index of Pj and Pi. Then, there are (J − 2)!/(J −M − 1)! total orderings of the remaining M − 1 elements. Thus, we have,
I(πM+1;w) ≤ 1 J(J − 1) ∑
1≤i6=j≤J
DKL ( P̄−i‖P̄−j ) ≤ 1 J(J − 1) (J −M − 1)! (J − 1)! M(J − 2)! (J −M − 1)! ∑ 1≤i 6=j≤J DKL (Pj‖Pi)
= M J(J − 1)2 ∑
1≤i 6=j≤J
DKL (Pj‖Pi)
These results together provide an immediate proof of Corollary 1.
Corollary 1. Assume the same setting as in Theorem 1. Then,
R∗P(β) ≥ ψ(δ)
1− 1 + ( Mn (J−1) + k ) 1 J2 ∑ 1≤i,j≤J DKL (Pi‖Pj)
log2 J  . Proof. Putting together the results of Theorem 1, Lemma 3, and Lemma 4, and using the fact that DKL (Pi‖Pj) ≤ α, the result follows immediately.
Corollary 2. Assume the same setting as in Theorem 1, with M + 1 < J . Then,
R∗P ≥ ψ(δ)
( log2(J −M)− kJ2 ∑ 1≤i,j≤J DKL (Pi‖Pj)− 1
log2 J
) .
Proof. This result follows as an application of the data processing inequality. Notice that πM+1 → π1:M →W forms a Markov chain. Thus,
I(πM+1;W ) ≤ I(πM+1;π1:M ),
by the data processing inequality. We can compute I(πM+1;π1:M ) in closed form:
I(πM+1;π1:M ) = log J
J −M .
The proof is completed by plugging in the i.i.d local packing bound alongside the above.

heading: B.4 BOUNDS USING MIXTURE DISTRIBUTIONS
text: In this section we introduce tools to lower bound the minimax risk when the meta-training set is sampled from a mixture over the meta-training tasks, P̄1:M = 1M ∑M i=1 Pi. We note first that Theorem 1 can be reproduced exactly when W ∼ P̄1:M . Thus, we need only provide a local packing bound for the mixture distribution. In Lemma 5 we provide such a lower bound for the special case where M = J − 1, so that data is sampled from a mixture over the entire environment. Lemma 5 (Leave-one-task-out mixture local packing). Let J ⊂ P contain J distinct distributions such that ρ(θP , θP ′) ≥ 2δ for all P, P ′ ∈ J and let P̄−i = 1J−1 ∑ j 6=i Pj . Let π be a random ordering of the J elements, and define W |π to be a vector of n i.i.d samples from P̄−πM+1 . Then,
I(πM+1;W ) ≤ 1 (J − 1)J2 ∑
1≤i,j≤J
DKL (Pi‖Pj) .
Proof. From Lemma 3 (and some simple arithmetic) we have,
I(πM+1;W ) = 1
J J∑ i=1 DKL ( P̄−i‖P̄1:J ) .
Note that by the definition of the mixture distribution,
P̄1:J = J − 1 J P̄−i + 1 J Pi.
Using the convexity of the KL divergence,
I(πM+1;W ) = 1
J J∑ i=1 DKL ( P̄−i ∥∥∥J − 1 J P̄−i + 1 J Pi )
≤ 1 J J∑ i=1 J − 1 J DKL ( P̄−i‖P̄−i ) + 1 J DKL ( P̄−i‖Pi ) = 1
J2 J∑ i=1 DKL ( P̄−i‖Pi ) = 1
J2 J∑ i=1 DKL  1 J − 1 ∑ 1≤j≤J,j 6=i Pj ∥∥∥Pi 
≤ 1 (J − 1)J2 J∑ i=1 ∑ 1≤j≤J,j 6=i DKL (Pj‖Pi)
= 1 (J − 1)J2 ∑
1≤i,j≤J
DKL (Pi‖Pj) .
Noting for the last step that the KL is zero if and only if the distributions are the same almost everywhere.

heading: B.5 PROOF OF HIERARCHICAL LINEAR MODEL LOWER BOUND
text: Recall that the space of distributions we consider is given by,
PLR = {pθ(y) = N (Xθ, σ2I) : θ ∈ B2(1), X ∈ Rn×d.} Theorem 3 (Meta linear regression lower bound). Consider PLR defined as above and let `(a, b) = (‖a− b‖2)2. If d ≥ 2 and 2−dM + kn−1 ≥ max{ d4β , dσ 2/(256γ2n), then,
R∗PLR(β) ≥ O (
dσ2
γ2(2−dnM + k) ) Proof. The proof consists of two steps, we first construct a 2δ-packing of PLR. Then, we upper bound the KL divergence between two distributions in this packing and use Corollary 1 to give the desired bound.
The maximal packing number J for the unit 2-norm ball can be bounded by the following,( 1
δ
)d ≤ J ≤ ( 1 + 2
δ
)d .
We use a common scaling trick. First, through this bound, we can build a packing set, V , with packing radius 1/2, giving 2d ≤ J ≤ 5d. We define a new packing set of the same cardinality by taking θi = 4δvi for all vi ∈ V (requiring δ ≤ 1/2). Giving for all i 6= j,
‖θi − θj‖ = 4δ‖vi − vj‖ ≥ 2δ similarly, ‖θi − θj‖ ≤ 4δ. We now proceed with bounding the KL divergences.
DKL (Pi‖Pj) = 1
2σ2 ‖Xiθi −Xjθj‖22
= 1 2σ2 ( θ>i X > i Xiθi + θ > j X > j Xjθj − 2θ>i X>i Xjθj ) ≤ 1
2σ2 ( niγ 2 i ‖θi‖2 + njγ2j ‖θj‖2 − 2θ>i X>i Xjθj ) where γ2i = supθ ‖Xiθ‖√ ni‖θ‖ . We write n = maxk nk and γ = maxk γk, then,
DKL (Pi‖Pj) ≤ nγ2
2σ2
( ‖θi‖2 + ‖θj‖2 − 2
nγ2 θ>i X > i Xjθj ) ≤ nγ 2
2σ2 ( ‖θi‖2 + ‖θj‖2 + 2‖θi‖‖θj‖ ) = nγ2
2σ2 (‖θi‖+ ‖θj‖)2 ≤
32nγ2δ2
σ2 ≤ β
The second line is derived using the Cauchy-Schwarz inequality, and the final inequality uses ‖θi‖ = ‖4δvi‖ ≤ 4δ. We will not proceed by invoking Corollary 1 on this packing set. This will require choosing δ to achieve our desired rate and will in turn impose constraints on the problem dimensions to ensure the packing is valid.
Now, using Corollary 1,
R∗PLR ≥ δ 2
( 1− (nM2 −d + k)32γ2δ2/σ2 + 1
d
) ,
Choosing δ2 = dσ2/ [ 128γ2(2−dMn+ k) ] gives,
1− (nM2 −d + k)32δ2/σ2 + 1
d = 1− d/4 + 1 d ≥ 1/4,
for d ≥ 2. To enforce δ ≤ 1/2, we further require that,
2−dMn+ k ≥ dσ 2
256γ2
Additionally, we may only consider packing sets with KL divergence no more than β, hence we also require that,
2−dM + kn−1 ≥ d 4β
Thus,
R∗P ≥ O (
dσ2
γ2(2−dnM + k)
)

heading: C HIERARCHICAL BAYESIAN LINEAR REGRESSION UPPER BOUNDS

heading: C.1 SOME USEFUL LINEAR ALGEBRA RESULTS
text: Let smax(A) denotes the maximum singular value of A; smin(A) denotes the minimum singular value of A.
Lemma 6. Singular value of sum of two matrices Let A,B ∈ Rm×n, then smax(A) + smax(B) ≥ smax(A+B). Furthermore, if A,B are positive definite, smin(A) + smin(B) ≤ smin(A+B).
Proof. The first result follows immediately from the triangle inequality of the matrix norm ‖·‖2. For the second result, suppose that A and B are positive definite.
smin(A+B) = inf ‖u‖=1
‖(A+B)u‖ (3)
= √
inf ‖u‖=1
‖(A+B)u‖2 (4)
= √
inf ‖u‖=1
‖Au‖2 + ‖Bu‖2 + 2〈Au,Bu〉 (5)
= √
inf ‖u‖=1
‖Au‖2 + ‖Bu‖2 + 2u>A>Bu (6)
(7)
Now, notice that A>B is similar to the matrix A1/2BA1/2, which exists as A is positive definite. This matrix is itself positive definite, and thus has non-negative eigenvalues, meaning A>B also has all positive eigenvalues. Thus, u>A>Bu ≥ 0, for all u, and,
smin(A+B) ≥ √
inf ‖u‖=1
‖Au‖2 + ‖Bu‖2 (8)
≥ √
inf ‖u‖=1 ‖Au‖2 + inf ‖v‖=1 ‖Bv‖2 (9)
≥ √ smin2(A) + smin2(B) (10) ≥ smin(A) + smin(B) (Concavity of √ ·) (11)
Lemma 7. Singular value of product of two matrices Let A,B ∈ Cn×n, then smax(A)smax(B) ≥ smax(AB), and, smin(A)smin(B) ≤ smin(AB).
First we prove the maximum singular value.
Proof.
smax(AB) = sup ‖v‖=1
√ v∗B∗A∗ABv (12)
= sup ‖v‖=1
√ ‖Bv‖2u∗A∗Au for u = Bv
‖Bv‖ , (13)
≤ sup ‖v‖=1,‖u‖=1
√ ‖Bv‖2u∗A∗Au (14)
= √
sup ‖v‖=1 ‖Bv‖2 sup ‖u‖=1 ‖Au‖2 (15)
= √ smax2(B)smax2(A) (16)
= smax(A)smax(B). (17)
The minimum singular value follows a similar structure. Suppose AB is full rank,
smin(AB) = inf ‖v‖=1
√ v∗B∗A∗ABv (18)
= inf ‖v‖=1
√ ‖Bv‖2u∗A∗Au for u = Bv
‖Bv‖ , (19)
≥ inf ‖v‖=1,‖u‖=1
√ ‖Bv‖2u∗A∗Au (20)
= √
inf ‖v‖=1 ‖Bv‖2 inf ‖u‖=1 ‖Au‖2 (21)
= √ smin2(B)smin2(A) (22)
= smin(A)smin(B). (23)
If AB is not full rank, then smin(AB) = smin(A)smin(B) = 0.
Lemma 8. (Von Neumann’s Trace Inequality (Von Neumann, 1937)) Given two n × n complex matrices A,B, with singular vales a1 ≥ . . . ≥ an and b1 ≥ . . . ≥ bn respectively. We have,
|Tr(AB)| ≤ n∑ i=1 aibi
This is a classic result whose proof we exclude.
As a direct consequence of Lemma 8, |Tr(AB)| ≤ na1b1.

heading: C.2 POSTERIOR ESTIMATE
text: For reference, we reproduce the posterior estimate for the true parameters θM+1. As a shorthand, we write Y1:M+1 = (y1, . . . ,yM+1).
p(τ |Y1:M ) = N (µτ |Y1:M ,Στ |Y1:M ), (24)
Σ−1τ |Y1:M = M∑ i=1 X>i (σ 2 θXiX > i + σ 2 1I) −1Xi, (25)
µτ |Y1:M = Στ |Y1:M M∑ i=1 X>i (σ 2 θXiX > i + σ 2 1I) −1yi (26)
p(θM+1|Y1:M ,yM+1) = N (µθM+1|Y1:M+1 ,ΣθM+1|Y1:M+1), (27) Σθ+τ |Y1:M = σ 2 θI + Στ |Y1:M (28)
Σ−1θM+1|Y1:M+1 = σ −2 M+1X > M+1XM+1 + Σ −1 θ+τ |Y1:M (29) µθM+1|Y1:M+1 = ΣθM+1|Y1:M+1(σ −2 M+1X > M+1yM+1 + Σ −1 θ+τ |Y1:Mµτ |Y1:M ) (30)

heading: C.3 UPPER BOUND FOR META LINEAR REGRESSION
text: In this section we prove the main upper bound result of our paper, Theorem 4.
Theorem 4 (Meta Linear Regression Upper Bound). Let θ̂M+1 be the maximum-a-posteriori estimator, µθM+1|Y1:M+1 . Then,
R∗PLR ≤ sup θ1,...,θM+1∈B2(1)
E[‖θ̂M+1 − θM+1‖2] ≤ O ( dσ2M+1C(M,n, k) −2D(M,n, k) )
where,
C(M,n, k) = k + Mn n(M+κ2)s22
α2 +A
 , and, D(M,n, k) = [k + Mn ( nL1 +A1)( Mn L2 +A2) ] .
Expectations are taken over the data conditioned on θ1, . . . ,θM+1. Additional terms not depending on d, M, n, k are defined in Appendix C.2.
Before proceeding with the proof, we introduce some additional notation and technical results.
Additional notation To alleviate (only a little of) the notational clutter, we will define the following quantities,
• Σ′ = ΣθM+1|Y1:M+1 • Σ′0 = Σθ+τ |Y1:M . • smin(X/ √ n) = s1 • smin(XM+1/ √ k) = s2 • smax(X/ √ n) = γ1 = κs1 • smax(XM+1/ √ k) = γ2 = κM+1s2
• α1 = σ21/σ2θ • α2 = σ2M+1/σ2θ • L = α2
(M+κ2)s22
• L1 = α1s21s22κ2M+1 • L2 = κ̃κτα22s22κ2M+1 • A = s
2 2α1 s21α2
• A1 = s22κ2M+1
• A2 = α1s
2 2κ 2 M+1
κ2τs 2 1α2
As we have uniform bounds on the singular values of all design matrices, we introduced an auxillary matrix X whose largest and smallest singular values are given by √ nγ1 and √ ns1 respectively.
We will also write S(A) = Cov[A,A], and κ(A) = smax(A)/smin(a) throughout.
Bias-Variance Decomposition As is standard, we can decompose the risk into the bias and variance of the estimator:
E[‖θ̂M+1 − θM+1‖2] = E[Tr((θ̂M+1 − θM+1)(θ̂M+1 − θM+1)>)] (31) = Tr(E[(θ̂M+1 − θM+1)(θ̂M+1 − θM+1)>]) (32) = Tr(Cov[θ̂M+1, θ̂M+1]) + Tr(E[(θ̂M+1 − θM+1)]E[(θ̂M+1 − θM+1)]>)
(33)
In the next two sections, we will derive upper bounds on the bias and variance terms above.
C.3.1 VARIANCE TECHNICAL LEMMAS
We first decompose the variance into contributions from two sources: the variance from data in the novel task and the variance from data in the source tasks.
Lemma 9. (Variance decomposition) Let θ̂M+1 = µθM+1|Y1:M+1 as defined above. Then the variance of the estimator can be written as
Tr(S(θ̂M+1)) = Tr(Σ ′σ−2M+1X > M+1XM+1Σ ′) + Tr(S(Σ′Σ′0 −1 µτ |Y1:M ))

heading: Proof.
text: Tr(Cov[θ̂M+1, θ̂M+1]) = Tr(S(Σ ′(σ−2M+1X > M+1yM+1 + Σ ′ 0 −1 µτ |Y1:M ))) (34)
= Tr(S(Σ′σ−2M+1X > M+1yM+1) + S(Σ ′Σ′0 −1 µτ |Y1:M )) (35)
= Tr(Σ′σ−2M+1X > M+1S(yM+1)σ −2 M+1XM+1Σ ′ + S(Σ′Σ′0 −1 µτ |Y1:M ))
(36)
= Tr(Σ′σ−2M+1X > M+1XM+1Σ ′) + Tr(S(Σ′Σ′0 −1 µτ |Y1:M )) (37)
We will now work towards a bound for each of the two variance terms in Lemma 9 separately. To do so, we will need to produce bounds on the singular values of terms appearing in Lemma 9.
We begin with the covariance term Σ′.
Lemma 10. (Novel task covariance singular value bound) Let L, A and s2 be as defined above. Then,
smax(Σ ′) ≤ σ2M+1 s22
[ k +
n Mn L +A
]−1 .
Proof. Using Lemma 6, we can bound smax(Σ′) as follows,
smax(Σ ′) = smax(ΣθM+1|Y1:M+1) (38)
= smax((σ −2 M+1X > M+1XM+1 + Σ −1 θ+τ |Y1:M ) −1) (39) = 1/smin(σ −2 M+1X > M+1XM+1 + Σ −1 θ+τ |Y1:M ) (40) ≤ 1/(smin(σ−2M+1X > M+1XM+1) + smin(Σ −1 θ+τ |Y1:M )) (41) = 1/(smin(σ −2 M+1X > M+1XM+1) + 1/smax(Σθ+τ |Y1:M )) (42)
Now, using the auxillary matrix X ,
smax(Σ ′) ≤ [ smin(σ −2 M+1X > M+1XM+1) +
1
σ2θ + 1 M smax((X >C̃−1X)−1)
]−1 (43)
=
[ smin(X > M+1XM+1)
σ2M+1 +
1
σ2θ + 1 M 1 smin(X>C̃−1X)
]−1 (44)
≤
[ ksmin 2(XM+1/ √ k)
σ2M+1 +
1
σ2θ + 1 M 1 smin(X>C̃−1X)
]−1 (45)
≤ [ ks22 σ2M+1 + 1 σ2θ + 1 M 1 smin(X>(Xσ2θIX >+σ2I)−1X) ]−1 (46)
Above we have used Lemma 6 repeatedly, alongside the standard identity, smax(A−1) = smin(A)−1. We continue now, additionally using Lemma 7,
smax(Σ ′) ≤ [ ks22 σ2M+1 + 1 σ2θ + 1 M 1 smin(X>X)smin((Xσ2θIX >+σ21I) −1) ]−1 (47)
=  ks22 σ2M+1 + 1
σ2θ + smax(Xσ2θIX >+σ21I)
smin(X>X) −1 (48) ≤
 ks22 σ2M+1 + 1
σ2θ + 1 M
smax(Xσ2θIX >)+σ21
ns21 −1 (49) ≤
 ks22 σ2M+1 + 1
σ2θ + σ2θsmax(XX >)+σ21 ns21 −1 (50) =
 ks22 σ2M+1 + 1
σ2θ + 1 M
σ2θns 2 1κ 2+σ21 ns21 −1 (51) = σ2M+1
ks22 + Mnn(M+κ2) α2 + α1 s21α2 −1 (52) = σ2M+1 s22 [ k + n Mn L +A ]−1 . (53)
Next, we deal with terms appearing corresponding to the data from the source tasks.
Lemma 11. (Source tasks covariance singular value bound) Let C̃1 = σ2θXX> + σ21I , and write κ̃ = κ(C̃1) and κτ = κ(Στ |Y1:M ). Then,
smax 2(Σ−1θ+τ |Y1:MΣτ |Y1:M ) ≤ 1 2Mσ2θns 2 1
smax(C̃1)κτ + 1κ2τ
=: D1
and,
smax(σ 2 1C̃ −1 1 ) ≤ 1 ns21 α1 + 1 =: D2
Proof. Using Lemma 6 and Lemma 7 we have,
smax 2(Σ−1θ+τ |Y1:MΣτ |Y1:M ) = smax 2(Σ−1θ+τ |Y1:MΣτ |Y1:M ) (54)
≤ smax2(Σ−1θ+τ |Y1:M )smax 2(Στ |Y1:M ) (55) = smin −2(Σθ+τ |Y1:M )smax 2(Στ |Y1:M ) (56) = smin −2(σ2θI + Στ |Y1:M )smax 2(Στ |Y1:M ) (57)
≤ smax(Στ |Y1:M )
2
(σ2θ + smin(Στ |Y1:M )) 2
(58)
Now, using σ2θ > 0,
smax(Στ |Y1:M ) 2
(σ2θ + smin(Στ |Y1:M )) 2 ≤
smax(Στ |Y1:M ) 2
2σ2θsmin(Στ |Y1:M ) + smin(Στ |Y1:M ) 2
(59)
≤ 1 2σ2θ
smax(Στ|Y1:M )κτ + 1κ2τ
(60)
Introducing the auxillary matrix X and using Lemma 6 and Lemma 7 on Στ |Y1:M , we have
1 2σ2θ
smax(Στ|Y1:M )κτ + 1κ2τ
≤ 1 2Mσ2θsmin(X >C̃−1X)
κτ + 1κ2τ
, (61)
where,
smin(X >C̃−11 X) ≥
smin(X >X)
smax(C̃1) (62)
= ns21
smax(C̃1) . (63)
This gives the first stated inequality,
smax 2(Σ−1θ+τ |Y1:MΣτ |Y1:M ) ≤ 1 2Mσ2θns 2 1
smax(C̃1)κτ + 1κ2τ
=: D1 (64)
The second follows as,
smax(σ 2 1C̃ −1 1 ) = σ21 smin(σ2θXX > + σ21I) (65)
≤ σ 2 1
smin(σ2θXX >) + smin(σ21I)
(66)
≤ σ 2 1
ns21σ 2 θ + σ 2 1
(67)
= 1
ns21 α1
+ 1 =: D2 (68)
In Lemma 11, we introduced additional condition numbers, which we can bound as follows,
κ̃ = κ(C̃1) = κ(σ 2 θXX > + σ21I) ≤ κ(σ2θXX>) ≤ κ(σ2θXX>)κ(σ2θI) = κ2, (69) κτ = κ(Στ |Y1:M ) ≤ κ(X >X)κ(C̃1) = κ 2κ̃ ≤ κ4. (70)
C.3.2 VARIANCE UPPER BOUND
We are now ready to put the above technical results together to achieve a bound on the variance of the estimator. Lemma 12. (Variance bound)
Tr(S(θ̂M+1)) ≤ κ2M+1σ 2 M+1
s22 d
[ k +
n n L +A
]−2 [ k +
Mn
( nL1 +A1)( Mn L2 +A2)
]
Proof. First, by Lemma 9 we can decompose the overall variance into two terms:
Tr(S(θ̂M+1)) = Tr(Σ ′σ−2M+1X > M+1XM+1Σ ′) + Tr(S(Σ′Σ′0 −1 µτ |Y1:M ))
We deal with the left term first.
Using trace permutation invariance and the von Neumann trace inequality (Lemma 8). We can upper bound the left variance term as follows,
Tr(Σ′σ−2M+1X > M+1XM+1Σ ′) = σ−2M+1Tr(Σ ′Σ′X>M+1XM+1) (71)
≤ dkσ−2M+1smax(Σ ′)2smax 2(XM+1/ √ k) (72) = dkσ−2M+1smax(Σ ′)2s22κ 2 M+1 (73)
For the second variance term, we observe that,
Tr(Σ′Σ′0 −1 S(µτ |Y1:M )Σ ′ 0 −1 Σ′) (74)
= Tr(Σ′Σ′0 −1 S(Στ |Y1:M M∑ i=1 X>i (σ 2 θXiX > i + σ 2 1I) −1yi)Σ ′ 0 −1 Σ′) (75) ≤MTr(Σ′Σ′0 −1 Στ |Y1:MX >C̃−1S(y1)C̃ −1XΣτ |Y1:MΣ ′ 0 −1 Σ′) (76) = MTr(Σ′Σ′0 −1 Στ |Y1:MX >C̃−11 σ 2 1IC̃ −1 1 XΣτ |Y1:MΣ ′ 0 −1 Σ′) (77) ≤Msmax(Σ′)2smax2(Σ−1θ+τ |Y1:MΣτ |Y1:M )σ 2 1Tr(X >C̃−1C̃−1X) (78)
Using Lemma 11, we have,
Tr(Σ′Σ′0 −1 S(µτ |Y1:M )Σ ′ 0 −1 Σ′) ≤ smax(Σ′)2MD1D2Tr(X>X)smax(C̃−11 ) (79) ≤ smax(Σ′)2MD1D2 min(n, d)nsmax(C̃−11 ) (80)
≤ smax(Σ′)2D2 M min(n, d)n
2Mσ2θns 2 1smin(C̃1)
smax(C̃1)κτ + smin(C̃1)κ2τ
(81)
≤ smax(Σ′)2D2 M min(n, d)n
2Mσ2θns 2 1smin(C̃1)
smax(C̃1)κτ + σ21 κ2τ
(82)
≤ smax(Σ′)2D2 min(n, d)n
σ2M+1 M 2Mn κ̃κτα2 + α1 κ2τσ 2 1 2α2
(83)
≤ smax(Σ ′)2
σ2M+1 nd ns21 α1 + 1 M 2Mn κ̃κτα2 + α1 κ2τs 2 1α2
(84)
Finally, rearranging and using Lemma 10, we can bound the sum of the two terms in the variance as follows,
Tr(S(θ̂M+1)) ≤ smax(Σ
′)2
σ2M+1 (kds22κ 2 M+1 + nd ns21 α1 + 1 M 2Mn κ̃κτα2 + α1 κ2τs 2 1α2 ) (85)
≤ smax(Σ
′)2s22κ 2 M+1
σ2M+1 (kd+
nd ns21s 2 2κ 2 M+1
α1 + s22κ 2 M+1
M 2Mns22κ 2 M+1
κ̃κτα2 +
α1s22κ 2 M+1
κ2τs 2 1α2
)
(86)
≤ κ2M+1σ 2 M+1
s22
[ k +
n n L +A ]−2 · (87)kd+ Mnd
( ns21s 2 2κ 2 M+1
α1 + s22κ 2 M+1)(
2Mns22κ 2 M+1
κ̃κτα2 +
α1s22κ 2 M+1
κ2τs 2 1α2
)  (88) ≤ κ2M+1σ 2 M+1
s22 d
[ k +
n n L +A
]−2 [ k +
Mn
( nL1 +A1)( Mn L2 +A2)
] (89)

heading: C.3.3 BOUNDING THE BIAS
text: Lemma 13. (Bias upper bound) Given θ1, . . . ,θM+1 ∈ B2(1), we have,
E[(θ̂M+1 − θM+1)] ≤ O d k + Mn
n(M+κ2)s22 α2 +A
−2 
Proof. The bias can be computed as follows,
E[(θ̂M+1 − θM+1)] = EµθM+1|Y1:M+1 − θM+1 (90) = ΣθM+1|Y1:M+1E(σ −2 M+1X > M+1y2 + Σ −1 θ+τ |Y1:Mµτ |Y1:M )− θM+1 (91)
= ΣθM+1|Y1:M+1(σ −2 M+1X > M+1XM+1θM+1 + Σ −1 θ+τ |Y1:MEµτ |Y1:M )− θM+1
(92)
= (σ−2M+1X > M+1XM+1 + Σ −1 θ+τ |Y1:M ) −1· (93)
(σ−2M+1X > M+1XM+1θM+1 + Σ −1 θ+τ |Y1:MEµτ |Y1:M )− θM+1
(94)
= (F +G)−1(FθM+1 +Gµτ |Y1:M )− θM+1 (95) = (F +G)−1FθM+1 − (F +G)−1(F +G)θM+1 + (F +G)−1GEµτ |Y1:M
(96)
= (F +G)−1G(Eµτ |Y1:M − θM+1), (97) where we wrote F = σ−2M+1X > M+1XM+1, and G = Σ −1 θ+τ |Y1:M . Thus,
E[(θ̂M+1 − θM+1)]>E[(θ̂M+1 − θM+1)] ≤ ‖(F +G)−1‖22‖G‖22‖Eµτ |Y1:M − θM+1‖ 2 2
We can bound each term in turn. First, note that ‖G‖22 ≤ 1/σ2θ , and we have bounded ‖(F +G)−1‖22 above. We can write,
‖Eµτ |Y1:M − θM+1‖ 2 2 = ∥∥∥∥∥Στ |Y1:M ( M∑ i=1 X>i C̃ −1 i Xiθi ) − θM+1 ∥∥∥∥∥ 2
2
‖Eµτ |Y1:M − θM+1‖ 2 2 = ∥∥∥∥∥Στ |Y1:M ( M∑ i=1 X>i C̃ −1 i Xiθi ) − Στ |Y1:MΣ −1 τ |Y1:MθM+1 ∥∥∥∥∥ 2
2
= ∥∥∥∥∥Στ |Y1:M M∑ i=1 X>i C̃ −1 i Xi(θi − θM+1) ∥∥∥∥∥ 2
2
≤ ( M∑ i=1 ‖Στ |Y1:M ‖2 ‖X > i C̃ −1 i Xi(θi − θM+1)‖2 )2
≤ ( M∑ i=1 ‖Στ |Y1:M ‖2 ‖X > i C̃ −1 i Xi‖2 )2 The last line follows from the fact that the parameters lie in a ball of unit radius. We now proceed by bounding the sum by M times the supremum — with some light abuse of notation,
‖µτ |Y1:M − θM+1‖ 2 2 ≤ (smax(X>C̃−1X)smax(XC̃−1X))2
= smax(X >C̃−1X)4 ≤ O(1)
Thus, overall the convergence of the bias is bounded by,
E[(θ̂M+1 − θM+1)]>E[(θ̂M+1 − θM+1)] ≤ O(smax(Σ′)2) ≤ O d k + Mn
n(M+κ2)s22 α2 +A
−2 
The proof of Theorem 4 is given by the combination of Lemma 12 and Lemma 13, and the biasvariance decomposition of the risk .

heading: D ADDITIONAL EXPERIMENT DETAILS

heading: D.1 HIERARCHICAL BAYES EVALUATION
text: We sample M linear models according to the hierarchical model in Section 5, with design matrices constructed by uniformly sampling points, x ∼ U [−1, 1], and storing the vector xj = xj , for i = 0, . . . , d in each row of Xi.
To produce the plots in Figure 2 we computed the average loss over 100 random draws of the training data and labels from the same set of fixed θ1:M+1 values. The θ values were sampled once from the hierarchical model with τ = [0, 1, 2, 0, 0, 3, 1], and σ2θ = 0.1
Code to reproduce these plots is provided in the supplementary materials with our submission.

heading: D.2 SINUSOID REGRESSION WITH MAML
text: Hyper parameters Description σ noise at test time. M number of tasks at the training tasks Mq number of tasks at the testing tasks eps per batch episode per batch train ampl range range of amplitude at training train phase range range of phase at training val ampl range range of amplitude at testing val phase range range of phase at testing inner steps number of steps of Maml inner lr learning rate used to optimize parameter of the model meta lr used to optimize parameter of the meta-learner n number of datapoints at training tasks(support set) k number of datapoints at testing tasks (support set) nq number of datapoints at training tasks (query set) . kq number of datapoints at testing tasks (query set).
For all of these experiments we used a fully connected network with 6 layers and 40 hidden units per layer. The network is trained using the MAML algorithm (Finn et al., 2017) with 5 inner steps using SGD with an inner learning rate of 10−3. We used Adam for the outer loop learning with a learning rate of 10−3.
Expected error was computed after 500 epochs of optimization and was averaged over 30 runs. We produced our results through a comprehensive grid search over 72 combinations of the settings below and it required around 30 minutes to produce the output of each setting, using a system with 1 gpu and 3 cpus. This experiment therefore lasted 20 hours in total. M = 50, n ∈ {20, 200}, k ∈ {100, 1000}, σ ∈ [10−8, 1.5],Mq = 100, eps per batch = 25, train ampl range = [1, 4], train phase range = [0, π/2], val ampl range = [3, 5], val phase range = [0, π/2], inner steps = 5, inner lr = 10−3, meta lr = 10−3

Review summaries:
The paper studies the information-theoretic lower bounds in the minimax setting of meta-learning. The paper also discusses upper and lower bounds in the hierarchical Bayesian framework of meta linear regression. The novelty of the paper is two-fold: a) it proves a novel meta-learning local packing result to compute the conditional information between training task samples and the novel task data distribution and b) it compares the lower bound of the risk to the risk of posterior estimate in meta linear regression. In addition, the authors verify the dependence of risk on various parameters in 2 different experiments.

This paper provides a minimax novel-task risk lower bound for meta learning via information-theoretical techniques, showing the fundamental limits of meta learning. The novel-task minimax risk depends on the number of samples from the meta-training set and novel task, as well as the task similarity. The authors further investigate the meta learning problem on a hierarchical Bayesian model, discuss the lower bound and upper bound with maximum-a-posterior estimator.