Theoretical bounds on estimation error for meta-learning
Authors: James Lucas
Mengye Ren
Irene Raissa KAMENI KAMENI
Toniann Pitassi
Richard Zemel
Venue: ICLR 2021 Poster (2021)
Keywords: meta learning
few-shot
minimax risk
lower bounds
learning theory

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.

Published as a conference paper at ICLR 2021
THEORETICAL BOUNDS ON ESTIMATION ERROR FOR META-LEARNING
James Lucas, Mengye Ren, Irene Raissa KAMENI KAMENI, Toniann Pitassi & Richard Zemel
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 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 inffrmmttion-thooree algorithms that are trained on data from multiple sources and tested on novel data. Our bounds depend intuitively on the information shared between sources data, and characterize the difficulty learning in this setting for arbitrary algorithms. We demonstrate these bounds meta-learning, computing both upper and lower bounds on parameter estimation via saakiimmm---psteerinn inference.
lower-bounds on minimax rates of convergence for
hierarchical Bayesian model of
INTRODUCTION
Many practical machine learning applications deal with distributional shift from training to testing. One example few-shot classification (Ravi & Larochelle| [2016] Vinyals et al.) 20166), where new classes need to be learned at test time based only 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 set of meta-training distributions, or tasks. At test-time, the learner is exposed to only 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 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 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- et al.) 2010: Amit & Meir 2017p. yet to our knowledge, the inherent difficulty of these tasks relative to the L..d case has not been characterized.
In this work, we derive novel bounds for meta learners. We first present general information theoretic lower bound, Theorem | 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 particular meta-learning setting. In recent work, Grant let al. (2018) recast the popular meta-learning algorithm MAMI. (Finn et al. (017)) in terms of inference in Bayesian hicrarchical model. Following this, we provide theoretical analysis of hicrarchical Bayesian model for meta-linnear-rerresiion We compute sample complexity bounds for posterior inference under Empirical Bayes (Robbins) 1956) this model and compare them to our predicted lower-bound, in the minimax framework. Furthermore, through asymptotic analysis of the error rate of the MAP estimator, we identify crucial features of the meta- meta-learning environment which are necessary for novel task generalization.
Note that this definition encompasses few-shot learning.

---

Published as a conference paper at ICLR 2021
Our primary contributions can be summarized as follows:
We introduce novel lower bounds on minimax risk of parameter estimation in meta-learming.
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 the enror rate for estimation in hierarchical meta-linear regression problem, which we verify through an empirical evaluation.
2 RELATED WORK
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-lcarning (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 general two-stage approach, which matches the standard meta-learning paradigm (Vilalta & Drissi 2002). In the first stage 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, 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 particularly important in safety-critical systems, for example in medical diagnosis.
Mousavi Kalan et (020) study the minimax risk of transfer learning. In their setting, the learner is provided with large amount of data from a single source task and is tasked with generalizing to target task with 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 large volume of prior work studying upper-bounds on generalization error in multi-task environments (Ben- David & Borbely, 2008 BBen-David et al. 2010, Pentina & Lampert 2014
Amit & Meir 2017 Mehta et al. 2012). While the approaches in these works vary, one common
Tactor is the need characterize mesk-relatedness Broadly, these approaches either assume shared
distribution for sampling tasks (Baxter 2000 Pentina & Lampert 2014 Amit & Meir 2017). or
measure of distance between distributions (Ben-David & Borbely 2008 Bev-David al. [2100]
Mohri & Medinal 2012). Our lower-bounds utilize a weak form of task relatedness, assuming that the environment contains finite set that is suitably separated in parameter space but close in KL divergence- set of assumptions also arises often when computing i.i.d minimax lower bounds (Lhh 2017).
One practical approach to meta-learning is learning linear mapping on top of a learned feature space. Prototypical Networks (Snell al. 2017) effectively learn discriminative embedding function and performs linear classification on top using the novel task data. Analyzing these approaches challenging due metric-learning inspired objectives (that require non-i.i. sampling) and the simultaneous learning of feature mappings and top-level linear functions. Though some progress has been made (Jin et al. 2009)] Saunshi 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 Hilbert space. Our results can be applied in these settings 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 syper-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, (016)., unsupervised learning (Metz et al. 2019). and reinforcement learning (Duan al. 2016). Yet another
2

---

Published as a conference paper at ICLR 2021
approach learns the initialization of task-specifie parameters, that are further adapted through regular gradient descent. Model-Agnostic Meta-Learning (Finn et al. 2017). D. or MAML, augments the global parameters with inttiliiiiiaiintiinnn 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 a hierarchical environment of linear models and provide both lower and upper bounds the error of estimating the parameters of novel linear regression problem.
Lower bounding estimation error is critical component of understanding learning problems (and algorithms). Accordingly, there is large body of literature producing such lower bounds (Khas' min- skii 1979 Yang & Barron 1999 Loh, 2017). We focus on producing lower- for parameter estimation using local packing sets, but expect that extending these results to density estimation or non-parametric estimation is feasible.
NOVEL TASK ENVIRONMENT RISK
Most existing theoretical work studying out-of-distribution generalization focuses on providing upper-boune bounds on generalization performance (Ben-David et al. 2010; Pentina & Lampert 2014 Amit & Meir 2017). We begin by instead exploring the converse: what the best performance 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 short summary is given here. We consider algorithms that learn in an environment (2, P), with data domain Z X' x y and P space of distributions with support 2. In the typical i.i.d setting, the algorithm is provided training data S E 2* consisting of l: i.i.d samples from P E E.P
In the standard multi-task setting, we sample training data from set of training tasks J.....,Prr+.) C P. We extend this to a meta-learning, or novel-task setting by first draw- ing SI:: n training data points from the first M distributions, for a total of n.M samples. We call this the meta-training set. We then draw a small sample of novel data, called a support set, SM41 Zt, from PM+1-
Consider a symmetric loss function E(a, ((((a, b)) for non-decreasing & and arbitrary metric p. We seek to estimate the output of 0 P f2 functional that maps distributions to metric space Ω2 For example, (P) may describe the coefficient vector of a high-dimensional hyperplane when P is a space of linear models, and p may be the Euclidean distance.
The i.i.d minimax risk Before studying the meta-learning setting, we first begin with definition of the iid minimax risk that measures the worst-case error of the best possible estimator,
R" = inf sup Es ((0(S),0p))
(1)
PEP
For notational convenience, we denote the output of (PP) by 0p. The estimator for is denoted, : z² + Q2 and maps ls samples from P to an estimate of 0p.
Novel-task minimax risk In the novel-task setting, we wish estimate 0 the parameters of the novel task distribution PM+1- We consider two-stage estimators for P In the first stage, the meta-learner uses learning algorithm f SI:M + A that maps the meta-training set to an estimation algorithm, 0sy. 2 Q. In the second stage, the learner computes i 0gy (5M-1), the estimate of 0 P
The novel-task minimax risk is given by,
(B) = inf f
sup
E S Pla [L (f(()):)))Sxx+))000xx))) SM 1 P~
Pa M...PP
where O.- = (PI..... PM41) E P: DKL (PM41) < 3, for i = 1,...,M) This ensures a degree of relatedness between the novel and meta-training tasks.
The estimator for + now depends additionally on the Mn samples in SIM,, where only < Mn samples from Par+1 are available to the learner. Thus, Rÿ, addresses the domain shift expected at
3

---

Published as a conference paper at ICLR 2021
P1
P2
P3
(novel)
True fn
MAP
MLE
Samples
Figure I: Meta-learning ID-regression: The parameters a ID regression model are fitted from a small support set. The training distributions (Pi, P2, P3) give useful inductive bias for fitting Pa using only points. The MLE solution on the novel task for those 5 points is also displayed.
test-time the meta-leariin setting and allows the learner use data from multiple tasks. The goal of f is to learn an inductive bias from SI:M such that good estimate is possible with only k data points from PM+11 this setting, i is equivalent to the number of shots few-shot learning.
An example with meta-linear regression We present here short summary based on meta linear regression, which we will analyze in more detail in Section 5
In Figure D we show observed data samples from family of polynomial regression models. Our aim new polynomial function from limited
to output an algorithm which recovers the parameters observations- we choose MAP estimator which is described fully in Section 5 In the bottom right, we are given only 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
P = (yo (x 0,03) ,
x= [I........ 1ad1113
is the space of polynomial regression models, parameterized by 0. For this problem, we take E(0, 0) = ||@ 8113- In Figure tasks generated with p(0) = N for unknown, sparse, Rd Thus, each model is polynomial function with few large coefficients. The algorithm f. first takes samples from Pı, P2, P3 and computes an estimate, f. This estimate of r is then used to compute ((S++15))
argmaxe, F Swr+1. Note that this approach is able to learn the correct inductive bias from the data, without requiring carefully designed regularizer. The lower bounds we derive in Section can be applied to problems of this general type, and the upper and lower bounds in Section 5 apply specifically meta-learning linear regression.
INFORMATION THEORETIC LOWER BOUNDS ON NOVEL TASK GENERALIZATION
In this section, we first present our most general result: Theorem I Using this, we derive Corollary [ that gives lower bound in terms of the sample size in the training and novel tasks. Corollary recovers a well-known i.i.d lower bound (Theorem when Mn = O, and, importantly, highlights that the novel task data significantly more valuable than the training task data. Additionally, 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
4

---

Published as a conference paper at ICLR 2021
In Theorem [ assume that P contains J distinct 26 26-separated distributions but only M S 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 [.1, Recall f(a, b) = <b(((a b)) for non-decreasing v/2 and arbitrary metric p.
Theorem (Minimax novel task risk lower bound). Let J contain J distinct distributions such that p(Op, P 2 28 and DKL (P) I 3 for all P. P' E J. Let x be random ordering of the elements, and Z| be a vector of ii.d samples from P TM441 Further, define W W be an n x M matrix whose joh column consist of n i..d samples from Pa.. Then,
RT((3) 2 (6) (1- I(TTM+1: W) [( 2) 2) +1
logg
Note that 8 a property of the so-called packing set, J, and may depend on the sample size, 3, and other properties of P. For example, practical instances of this bound typically require eb() O1//k) or similar, as in Theorem bellow. To derive this result, we bound the statistical estimation error by the error corresponding decoding problem where we must predict the novel task index, given the meta-training set SI:M and SM++1- Fano's 's inequality provides best-case error rates for this problem.
Using Theorem [ derive first bound the novel-task minimax risk that depends 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 our 26 26-packing that are close (in terms of their pairwise KL distance), then learning novel task from training samples drawn from the meta veta-training tasks requires significantly more examples; in particular, learning the novel task from samples drawn from the meta training set requires (2J) 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 7 Then,
1
Mu [J-1] + k) fe Eisiess DRL. (PolP3)
(9) 2 (5)
loga
tighter bound on partially observed environments We now consider the special case of Theo- rem r 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 + < J. Then,
[log2(J M) 5/ Eisiges DKL (P:))P)) (P.1PP)-1) -
RC 2 (8)
log, J
In this work, we have focused on the setting where W contains equal number of samples from each of the meta-training tasks - this is the sampling scheme shown in Figure 2. However, is possible to extend these results different sampling schemes for W. For example, in the appendix we derive bounds with W IT as mixture distribution. Surprisingly despite task identity being hidden from the learner, the asymptotic rate for these two sampling schemes match.
4.1 MEASURING TASK- RELATEDNESS
The use of local packing requires the design of an appropriate set of distributions whose corresponding parameters are 25-separated but maintain small KI. divergences. 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 depend sample size and other problem-specific variables. As 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 a necessary feature for upper-bounds on novel task generalization, but are typically difficult define (see e.g. Ben--aviid & Borbely (2008)). Our lower bounds utilize
5

---

Published as a conference paper at ICLR 2021
relatively weak notion of resttrela,,,sess, and thus may be overly pessimistic compared 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 Li.d LEARNERS
From the statement of Theorem it is not clear how this lower-bound compares to that of the i.i.d learner which has access only to the l 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.d learners. To do so, we revisit standard minimax lower bounds that be found in e.g. Loh (2017).
Theorem (IID minimax lower-bound). Suppose [P....., Pr} S satisfy p(Op:: 0p,) 2 28 for all i x j. Then,
Rº 2 (0) (1
fr Eisuse DKL (P:IIP)) +1
log2 J
We include proof of this result in Appendix B.1 using local-packing in our meta-learning bounds. As hoped, [ recovers Theorem 2 when there are no training tasks available. Moreover, this i.dd bound is strictly larger than the one computed in Corollary [ 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 for our meta-learning minimax bounds. We investigate the quality of these bounds by providing comparable upper bounds in the next section.
ANALYSIS OF A HIERARCHICAL BAYESIAN MODEL OF META-LEARNING
Our goal is to analyze the sample complexity of meta-learning for linear regression, where samples drawn from multiple meta-trainin eeta-ttriinig tasks and want generalize data points. After introducing the setting, we will compute lower- bounds on the minimax risk using results from Section revealing 2 scaling 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 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- veea-training samples may significantly improve convergence in the small l: regime. This is validated empirically in Section 6
task with only few
For 1...M + 1, where M + the total number of tasks, we define,
y: = X,0, + Ei, 6 ~ N(
X; E maxd ys E R" R" E
of E R
Each task has some design matrix X; and unknown parameters 0,. For simplicity, we assume known isotropic noise models and that n4 = for S M, with WM++1 =
Our meta learner will fit the data using empirical Bayes estimate in hierarchical Bayesian model:
0, = TER,, & Rd,, & ~~N00, o²1), o R
We will consider the Maximum a Posterior estimator,
i p 1 = argmax 1( ..)+))
0
and will characterize its risk, 0 - M [3 where the expectation is with respect to sampled data only. The posterior distribution under the Empirical Bayes estimate for r is given in Appendix
C.2 C22 The derivation standard but dense and we recommend dedicated readers to consult (Gelman al. 2013), or equivalent text, for more details.

---

Published as a conference paper at ICLR 2021
5.1 MINIMAX LOWER BOUNDS
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 = (re(y) (NX00 o²T) E (1), E [Radd
where 0 the parameters be learned, and X the design matrix of each linear regression task in the environment. We write max; Tmax XX /n), which we assume is bounded for all X and (an assumption that validated for random Gaussian matrices by |Rasktti et al.) (20TT).
Theorem 3 (Meta linear regression lower bound). Consider PLR defined above and let E(a, b)
(Ila bl If d 2 2 and 2 M + kn- 2 max 43 do² (256/) then,
do²
R (8) 2 2222-AMM + R)
The proof is given in Appendix B.5 We see that the size of the meta-training set has an inverse expo- nential scaling in the dimension, d. This reflects the complexity of the space growing exponentially in dimensions and the need for matching growth in data size to cover the environment sufficiently.
5.2 MINIMAX UPPER BOUNDS
To compute upper bounds on the estimation error, we require an additional assumption. Namely, will assume that the design matrices also have bounded minimum singular values, 0 S Fuin (X/ /n) (see Raskutti et al. (2011) 1) for some justification). For the soper-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- veta-training tasks. We note that we can still recover the setting assumed special case.
in the lower bounds, where all tasks match these parameters,
The learner observes n data points from each linear regression model in { {Pa....., Par C C.P. We then bound the error of estimating 0s+1, for which & samples are available.
The expected error rate of the MAP estimator can be decomposed as the posterior variance and bias squared. In the appendix provide detailed derivation of these results. The bound depends dimensionality d, the observation noise in each task of, 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 (Meta Linear Regression Upper Bound). Let 0m41 the maximum-a-posterionn estima- tor, H0 Then,
RE
sup (1)
Elll 0 0Mt+1l [
where,
Mn k n(M++))
Mn
C(M, n,
and. D(M, n,
k
1/1
AI)
Mr T
+ A2)
Expectations are taken over the data conditioned on O,,..., Oas+1- Additional terms not depending on d, M, n, k 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, 0 In the following section, we will discuss some of the consequences of this result and its implications for our lower bounds.
5.3 ASYMPTOTIC BEHAVIOR OF THE MAP ESTIMATOR
We first notice that when small, the risk cannot be reduced to zero by adding more meta traiiing data. Recent work has suggested such relationship may be inevitable (Hanneke & Kpotufe 2020). Our lower bound presented in Corollary 2 aggrees that more samples from a small number of meta- training tasks will not reduce the error to However, unlike our lower bounds based local
7

---

Published as a conference paper at ICLR 2021
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 utilize for the lower-bounds when the number of tasks grows, and expect a sharper bound may be possible.
To emulate the fhw-shot learning setting where is relatively small, we consider oc, with k and M fixed. In this case, the risk bounded as,
sup 0 0.....OuHIIE E333(1)
B[110ar+1 0M+1l1] do
k
2ayM M R²
where a2 = MM /
. is the ratio of the observation noise to the variance in sampling 0, and is the condition number of the design matrices. This leads a key takeaway: if the observed samples from PM+1 vary considerably more than the parameters 0, then observing more samples in SI:M will significantly improve convergence towards the true parameters in the small & regime. Further, adding more tasks (increasing M) also improves these constant factors by removing the dependence on the condition number, K.
EMPIRICAL INVESTIGATIONS
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 this section can be found in Appendix D
6.1 HIERARCHICAL BAYES POLYNOMIAL REGRESSION
We first focus on the setting of polynomial regression over inputs in the range 11, Some examples of these functions and samples are presented in Figure 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 In Figure 2A. we varied the novel task difficulty by increasing the novel task observation noise (0141) 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 task was relatively difficult (blue vs. green), the expected loss was orders of magnitude lower when the novel task became easier. In Figure B, we fixed the relative task difficulty and instead varied and .. 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 non-zero asymptotic lower-bound - eventually it is more beneficial to add more novel-task data samples.
red). And while larger l made little difference when the novel
These empirical simulations verify that our theoretical analysis is predictive of the behavior of this meta learning algorithm, each of these observations can be inferred from Theorem g While this model simple, it captures key features of and provides insight into the more general meta-learning problem. We also explored 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.
6.2 SINUSOID REGRESSION WITH MAML
Following the connections between MAML and hierarchical Bayes explored by Grant al. (2018) 8).. 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 prior over the amplitude and phase. In other works (Finn et al. 2017, Grant 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.
8

---

Published as a conference paper at ICLR 2021
Expected error over varying novel lask difficulty
Expected error over varying dalasel sices
N- 2, 2.n 20, E 6000)
1/2
Reck
M.n.KK 20.5)
(M.n, - (50, 1000)
(M.n, A0 = 200.
13*
19'
1d
2000
400
0001
1:00
1900
12000
54000
Novol bask
samples (Mh
(A)
B
Figure 2: The expected emror rate of the hierarchical MAP estimator, 0M+1, different environ- ment hyperparameter settings. A) The novel task observation noise is increased, making the novel task harder learn. B) We increase the size of the dataset, one case adding new tasks (M) and in the other adding new novel task data samples (k).
We display the risk averaged over 30 trials in Fig- ure 3 We varied the novel task difficulty by in- creasing the observation noise in the novel task. We plot separate curves for different dataset size configurations, and observe that the empirical re- sults align fairly well with the results derived by sampling the hierarchical model (Figure ( Adding more meta- veta-training data (increasing πι) 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, the wins for in- creased meta-training and meta-testing data were consistent, until task noise prevents any setting of the model from performing the task.
[M. MM 20,100
[M.000-550 20.1000)
(M/nA)--50 200,1000)
124
104
Novel tooks n0
Figure 3: Average risk for regressing sinusoid functions with MAML.
CONCLUSION
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 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 gap between our lower and upper bounds when there are large number of training tasks, which we hypothesize is limitation of the proof technique that we applied derive the lower bounds- suggesting exciting direction for future research.
8 ACKNOWLEDGEMENTS
This work benefited greatly from the input of many other researchers. In particular, we extend our thanks to Shai
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 Canada through CIFAR, and companies sponsoring the Vector Institute (www. www.veettorisstiiio pttp://

---

Published as a conference paper at ICLR 2021
REFERENCES
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-bayes theory. arXiv preprint arXiv:1711.012:: 2017.
Marcin Andrychowicz, Misha Denil, Sergio Gomez Colmenarejo, Matthew W. Hoffman, David Pfau, Tom Schaul, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems 29, pp. 3981-3989 2016.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Shai Ben-David and Reba Schuller Borbely. A notion of task relatedness yielding provable multiple- task learning guarantees. Machine learning, 73(3):273-287, 2008
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1-2):151-17)) 2010.
Brian Bullins, Elad Hazan, Adam Kalai, and Roi Livni. Generalize across tasks: Efficient algorithms for linear representation learning. In Aurélien Garivier and Satyen Kale (eds.). Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pp. 235-246, Chicago, Illinois. 22-24 Mar 2019. PMLR. URL http://proceedingg mwr press http////////biiiieee html
Tianshi Cao, Marc Law, and Sanja Fidler. theoretical analysis the number of shots in few-shot learning, arXiv preprini urXiv:1909) 11722, 2019.
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil, Leamning-to-leam stochas- tic gradient descent with biased regularization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1566-1575, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09434 2020.
Yan Duan, John Schulman, Xi Chen, Peter L. Bartlett, Ilya Sutskever, and Picter Abbeel. RI Fast reinforcement learning via slow reinforcement learning. CoRR, abs/161 1.02779, 2016.
Robert Fano. Transmission of information. A Statistical Theory of Communication, 1961.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adaptation of deep networks. In Proceedings of the 34th International Conference Machine Learning Volume 70, pp. 1112-111 135. JMLR. org, 2017.
Andrew Gelman, John B Carlin, Hal S Stern, David B Dunson, Aki Vehtari, and Donald B Rubin. Bayesian data analysis. Chapman and Hall/CRC, 2013.
Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas Griffiths. Recasting gradient- based meta-learning hierarchical Bayes. arXiv preprint arXiv:/801.088 2018.
Steve Hanneke and Samory Kpotufe. On the value of target data transfer learning. In Advances in Neural Information Processing Systems 32, pp. 9871-9881. Curran Associates, Inc., 2019.
Steve Hanneke and Samory Kpotufe. A no-free-lunch theorem for multitask learning. arXiv preprint arXiv:2006. 15785, 2020.
Rong Jin, Shijun Wang, and Yang Zhou. Regularized distance metric learning:theory and algorithm. In Advances Neural Information Processing Systems 22, pp. 862-870, 2009.
Rafail Z Khas' minskii. lower bound on the risks of non non-mmractr estimates of densities in the uniform metric. Theory of Probability & Its Applications, 23(4):794-798, 1979.
10

---

Published as a conference paper at ICLR 2021
Mikhail Khodak, Maria-Florins Balcan, and Ameet Talwalkar. Provable guarantees for tradieent-bsee meta-learning. arXiv preprint arXiv:1902.10644 2019.
Samory Kpotufe and Guillaume Martinet. Marginal singularity, and the benefits of labels in covariate- shift. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 1882-1886. PMLR, 06-09 Jul 2018.
Po-Ling Loh. On lower bounds for statistical learning theory. Entropy, 19(11):617, 2017.
James Lucas, Mengye Ren, and Richard Zemel. cnoommtiiontheorettie limitations on novel task generalization. Neurips 2019 Workshop on Machine Learning with Guarantees, 2019.
Matthew MacKay, Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger B. Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In 7th International Conference on Learning Representations, 2019.
Andreas Maurer. Transfer bounds for linear feature learning. Machine learning, 75(3):327-350, 2009.
Nishant Mehta, Dongryeol Lee, and Alexander Gray. Minimax multi-task learning and generalized loss-compositional paradigm for mtl. Advances in Neural Information Processing Systems, 25: 2150-2158, 2012.
Luke Metz, Niru Maheswaranathan, Brian Cheung, and Jascha Sohl-Dickstein. Meta-learning update rules for unsupervised representation learning. 7th International Conference on Learning Representations, 2019.
Mchryar Mohri and Andres Munoz Medina. New analysis and algorithm for learning with drifting distributions. In International Conference on Algorithmic Learning Theory, pp. 124-138. Springer, 2012.
Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi. Minimax lower bounds for transfer learning with linear and one-hidden layer neural net- works. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1959 1969. Curran Asso- ciates, Inc., 2020. URL httpps://proccedings hewp:/ceeeeeddnneeeeeeeeeeeeeeee www..nnuu....ppppeeeeee cc/ppaper//22//Eeeeee
Anastasia Pentina and Christoph Lampert. A PAC-bayesian bound for lifelong learning, In Interna- lional Conference on Machine Learning, pp. 991-999, 2014.
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax rates of estimation for high-dimensional linear regression over f-g-balls. IEEE transactions on information theory, 57(10):6976-6994 2011.
Carl Edward Rasmussen and Hannes Nickisch. Gaussian processes for machine learning (GPML) toolbox. J. Mach. Learn. Res., 11:3011-3015, 2010.
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. International Conference Learning Representations, 2016.
Herbert Robbins. An empirical bayes approach to statistics. Proceedings of the Third Berkeley Symposium Mathematical Staristics and Probability, Volume 1: Contributions to the Theory of Statistics, pp. 157-163, Berkeley, Calif., 1956. University of California Press.
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In International Confer- on Machine Learning, pp. 5628-56311 2019.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems, pp. 4077-4087, 2017.
11

---

Published as a conference paper at ICLR 2021
Ricardo Vilalta and Youssef Drissi. A perspective view and survey of meta-learning. Artificial intelligence review, 18(2):77-95, 2002.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In Advances in neural information processing systems, pp. 3630-3638, 2016.
John Von Neumann. Some matrix- matrix-inequalitien and metrization of matric space. 1937.
Boyu Wang, Hejia Zhang, Peng Liu, Zebang Shen, and Joelle Pineau. Multitask metrie learning: Theory and algorithm. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 3362- 3371. PMLR, 16-18 Apr 2019.
Yuhong Yang and Andrew Barron. Information-theoretic determination of minimax rates of conver- gence. Annals of Statistics, pp. 1564-1599, 1999.
12

---

Published as a conference paper at ICLR 2021
A
NOTATION
Description
X
The domain of the data, e.g. Rd
The range of the data, c.g. IR
The product space A' x y
P
A collection of distributions over Z
J
A (finite) subset of distributions in P An element of P
P
pk
The product distribution, whose sam- ples correspond to k independent draws from
The product distribution, I1 Ps, for
P. E P
PreM
The mixture distribution, 37 EE P.. for P, E
Ω
A metric space, containing parameters for each distribution
functional, mapping distributions in P to parameters in Ω
0
An estimator 0: Z -
I(X;Y)
The mutual information between ran- dom variables X and Y.
S, SM8M1
Denotes training datasets drawn i.i.d from some E P. Typically (=1,--., 2n). SM ( =
Sp
Denotes meta veta-training drawn i.i. from PI:M
[N] for N E
Indicates the set {L...., N
Br(r)
The p-norm ball of radius r, centered 0.
Table I: Summary of notation used in this manuscript
B LOWER BOUND PROOFS
We will make use of several standard results below, which we present here.
Lemma Fano's Inequality (Fano, 1961; Cover Thomas, 2012) For any estimator Ý of random variable Y such that - + Y forms a Markov chain, it holds that,
F(Ý +Y) 2 - H(Y) ;(Y 2) -
log, [Y|
log, |Y|
Lemma 2. Mutual information equality (Khas' minskii Z1, Zz, Y, then,
1979) Consider random variables
(Y; 22)) + (121; 22) 1 (Zz, I(22))
Lemma 3. Local packing lemma Loh 2017) Consider distributions P.....,
.......E P1 E P. Let be random variable distributed uniformly on and let ( j) be vector of k i.i.d samples from
13

---

Published as a conference paper at ICLR 2021
Py. Then,
k I(: - J
Σ DKL (P:lP))))))
1S1JSJ
We will require novel local packing bound for the novel-task risk, which we present in Lemma
B.1 IID LOWER BOUND
We first prove the ii.d result, which will serve as a guide for our novel lower bounds.
Theorem (IID minimax lower- bower-bound.. Suppose {PI...., P,} S satisfy p(Op, 0p,) 2 28 for all i # j. Then,
R 2 (0)) (1-
à J Eisayes DRL. (P:l1 + -
log2 J
Proof. First, notice that,
sup Eg [(((()) PEP
1 Σ 2
Bs ((((())
i=1
Now define the decision rule,
f(S) argmin pl ((0(S), 0r,)), 1šj5J with ties broken arbitrarily. We proceed by bounding the expected loss. First, using Markov's inequality,
E Es [(((()) 2 (6)) S-PR (x)() 2 v()
= (b))PP (p(0(S),0n) 2 6)
Next, consider the case ((((S),8.) < 6. Through the triangle inequality,
(()(S), 0r,) 2 p(0r,, 6rG) p(((S), 0r.) 2 25 - 5 p(B(S),,p)
Thus, the probability that the distance is less than 8 is at least as large as the probability that the estimator is correct.
()) s. [((0(S),0g) 2 }())] 2 (())P(((S) +
Now, using Fano's ' inequality with Y #M+1, and Ý = f(S) (and the corresponding Markov chain TM+1 + S f()), we have,
F(F(S) loga J - Z) 1
log2 J
Combining the above inequalities with the Local Packing Lemma gives the final result.
B.2 PROOF OF THEOREM II
Theorem (Minimax novel task risk lower bound). Let J contain J distinct distributions such that p(Op, 0p.) > 28 and DRt. PP') S 3 for all P. Pt E J. Let n be random ordering of the elements, and Z be a vector of i.i.d samples from P P Further, define W W| to be an n. x matrix whose jth column consist of n i..d samples from Pa,- Then,
(B) 2 (6)) (1-
I(TMM+1: W) + 1(TM+11 Z) 2)+ +1
log, J
14

---

Published as a conference paper at ICLR 2021
Proof. As in the i.d case, first bound the supremum from below with average,
B (Pix)) [((OsLic (5M+1);0ppp)) 2
Σ
Bu (((0(t))0.))
sup
(J-1) M
Pi PM P EP
Sat (1
iml
m[(
where the inner sum is over all length M orderings, with TM+1 = i.
As before, consider the following estimator,
f(W, Z) = argmin ((0w
19J5J
Using Markov's inequality, and then following the proof of Theorem we have,
Σ
Ew- (2), 2-//
2
E
(()) Z) + 1|1]
J
i=
M
(
M
a[(FM(1=))
= (f)) Z) + MM++1
with the use of Fano's inequality, we arrive at,
v))) (1 M( (W, 2)) +
loga
Conditioned on Y, each element of W and Z are independent but they are not identically distributed. Thus, with the application of Lemma]] 2
[(T Z) ((TM41: ( (TM41;W)
The result follows by combining these inequalities.
Remark In the above proof of Theorem 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.
now proceed with proofs the corollaries of Section 4.
B.3 LOCAL PACKING RESULTS
Lemma (Meta-learning local packing). Consider the same setting as in Theorem 7 then
Mn Σ DKL (P:))3)
[(TM+1;W) JJJ-1) 15155J
Proof. There are (J- (J-1)1/(J M 1)! orderings the first M indices, given the (M + 1)th, We introduce the following notation,
P_, JJ-M I)!
Σ p(W]=)
P : 5 Σ P
(J
As in previous proofs, we notice that we can write,
p= 1 P-
P
J
J J-1 Σ P-j
15

---

Published as a conference paper at ICLR 2021
First, note that upper bound [(TM+1: W) W. Further,
(1M41 w), where w denotes single row in
P-
= J
E log
P
i=1
1
DKL.
P-ill P_
J - 1
E P-j
J
J-
j
1
- DKL ( 0F4
J J-1
(P-ilIP-s)
-
$ JJJ 1)
E ISW4SSJ
DEL (P-s
We will use convexity of the KL divergence to upper bound this quantity. Each distribution P-ş is an average over 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-,. Thus care only about selections that contain either j or i such that matching pairs of distributions exactly not possible. Further, 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 (P)).P:). We conclude by counting the total number of orderings producing such pairs. First, there are M choices for the index of P, and P.. Then, there are (J 2)1/(J M 1)! total orderings of the remaining M - elements. Thus, we have,
[TMM+1:W) 1 J(J - 1) ISitiSJ
Σ DEL (P-:I(P-j)
(J-M M - 1)! M(J 2)
DKL (P)
J(J 1)
(J 1J! (J-M
M 1)! ISH4
M
Σ
DEL (Pyl
J(J - 1)2
1S4415J
These results together provide immediate proof of Corollary 1.
Corollary 1. Assume the same setting in Theorem 7 Then,
1 (-11 + k fo Eisisss DKL. (P:lIP))
1 [
(3) 2 (0))
log, J
Proof. Putting together the results of Theorem 1, Lemma 3, and Lemma 4, and using the fact that DKL (Pr)P,)) S a, the result follows immediately.
Corollary 2. Assume the same setting as Theorem I, with M + < J. Then,
[logs(J - M) fa Ensryss DEL (P.))P,)
Rt 2 v1))
log, J
16

---

Published as a conference paper at ICLR 2021
Proof. This result follows an application of the data processing inequality. Notice that xM+1 TI:M + W forms Markov chain. Thus,
[TMM1iWW - (TM++17TMM)
by the data processing inequality. We can compute +1; in closed form:
J
[ (T log J
The proof is completed by plugging in the i.dd local packing bound alongside the above.
B.4 BOUNDS USING MIXTURE DISTRIBUTIONS
In this section we introduce tools to lower bound the minimax risk when the meta-training set is sampled from mixture over the meta-trainin meta-training tasks, PI-M = M E P.. We note first that Theorem | can be reproduced exactly when W ~ PI:M Thus, we need only provide a local packing bound for the mixture distribution. Lemma 5 we provide such a lower bound for the special case where M = = 1, that data is sampled from mixture over the entire environment.
Lemma (Leave-one-task-our mixture local packing). Let I C P contain J distinct distributions such that p(0p,0p) 2 25 for all P, P' E and let P_+ = - - Pj. Let be random
ordering of the elements, and define W T to be vector of n i..d samples from P P-RM Then,
I[TM+1: W) v (J-
1
Σ 1SJJ
DKL (P:lP))
Proof. From Lemma 3 (and some simple arithmetic) we have,
1 [(TM41; W) EDDe DKL (P-iIPP..))
f=1
Note that by the definition of the mixture distribution,
J-1 -
1 P jp:.
Pi.
Using the convexity of the KL divergence,
| J _ p_ + + p.)+jpp)
T(TM+1:W7
Σ
DKL
1=1
DKL. (P-:IIP->) + 1 DKi. (P-:IP.)
i=1
DRL. (P-ilP..)
J
Σ P. P3(PP. ISiJJjti
DKL
J 1=1
J
DKL (P31IP3)
1)J²
1=1 15J$JJ44
Σ
DEL (P:))P)).
1)J2
15KJ5J
Noting for the last step that the KL is zero if and only if the distributions are the same almost everywhere.
17

---

Published as a conference paper at ICLR 2021
B.5 PROOF OF HIERARCHICAL LINEAR MODEL LOWER BOUND
Recall that the space of distributions we consider is given by,
PLR (po(y) (X000 1) 0 B2(,), X BRxdd
Theorem (Meta linear regression lower bound), Consider PLR defined as above and let E(a, b) (Ila bll2) If d 2 2 and 2 2 + kn- 2 max 13 /256/)2 then,
do²
R (8) 2 22 +
Proof. The proof consists of two steps, first construct 25-packing of PLR- Then, upper bound the KL divergence between two distributions in this packing and use Corollary to give the desired bound.
The maximal packing number J for the unit 2-norm ball can be bounded by the following.
(1) S J 1
We use common scaling trick. First, through this bound, we can build packing set, V. with packing radius 1/2, giving 24 I S 5t. We define new packing set of the same cardinality by taking 0, 4ov; for all Us E V (requiring ō 1/2). Giving for all # j.
||0: 03 40flu;
Uzl 2 25
similarly, 10. 8, S 46.
We now proceed with bounding the KL divergences.
DKL (P))
20 |X,6; x,0,112
X, (0, X, X,0, + -X X,),
20
(n 0 1, -20, x; x,,,)
202
where 7/= =supa
|X,00| /
We write max; n2 and = max; 7k. then,
ny²
2
DKL (P:))P)) <
||0:1| + |0,
0 X x,0,
20²
n??
ny²
(110,11 |0 + 2 2 11
2g²
32n 82
n
(110,11
+ ||0, <
20
g²
The second line is derived using the Cauchy-Schwarz inequality, and the final inequality uses ||O.|| || |0vpl| S 46. We will not proceed by invoking Corollary on this packing set. This will require choosing 5 to achieve our desired rate and will in turn impose constraints on the problem dimensions to ensure the packing is valid.
Now, using Corollary
Re 2 82 (1 1- (nAf2- + + / + )
Choosing 8 = do² [128 (2 Mn + k)] gives,
(n.22- + k)3282 /02 +
d/4+1
2 1/4,
d
d
for d 2 2. To enforce 8 < 1/2, we further require that,
2
2 2- + k:
256y
18

---

Published as a conference paper at ICLR 2021
Additionally, may only consider packing sets with KL divergence than 8, hence also require that,
2 2- M + kn 2 43
Thus,
do²
Rp 2 0
(2(2--n.M +
C HIERARCHICAL BAYESIAN LINEAR REGRESSION UPPER BOUNDS
C.I. SOME USEFUL LINEAR ALGEBRA RESULTS
Let maax(() 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 E Rmxn then 8max (A) + 8max (B) 2
Smax B). Furthermore, if A, B are positive definite, 8min (A) 8 (B) & 8min (A B).
Proof. The first result follows immediately from the triangle inequality of the matrix norm ||-1|2-
For the second result, suppose that A and B are positive definite.
8 min (A B)
inf (A B)ull ||a||| =1
(3)
inf [[A + B)ul
(4)
|||]
inf
||u + Bul + 2(Au, Bu)
(5)
||]|==
inf
||ul| + Bull 1 + 2u AT Bu
(6)
V
[|]|==1
Now, notice that B is similar the matrix 1/2 B/2/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 AT Bu 2 0, for all u, and,
(A + B)
inf || | + ||Bu||2
(8)
||l||=
inf |uul| + inf |e
(9)
||a||=
|
w 8min ((A) + Smin (B)
(10)
(min(A) (A) + 5min (B)
Smin
(Concavity v.)
(11)
Lemma 7. Singular value of product of two matrices Let A, Cuxn, then Smax (max(A) (A)smax (
Smax Smax((A) (AB), and, Smin (A) (B) S Smin Smin(BB (AB).
First we prove the maximum singular value.
19

---

Published as a conference paper at ICLR 2021
Proof.
Smax (AB)
sup Vv* ABe
(12)
|||||=1
= sup v Bu Bul A Au for Bv
(13)
Bull
||v||=1
I sup
3 An
(14)
|||||=1|||||==
= sup
|ull |||||=|
sup ||uu|
(15)
V
||x||=1
Smax 2 (B)) (B)smax" (AA)
(16)
= Smax mA) (B).
(17)
The minimum singular value follows similar structure. Suppose AB is full rank,
8 mii (AB) = inf v AB |v||=1
(18)
inf Bl Fut ArAu for Br [i|==1
(19)
|Bo|]]
inf
2 A+Au
(20)
|||==1 u||=1
inf || Bull
inf ||
(21)
V ||||==1 |u] =1
V Smin ( (AA
(22)
Smin (A)s (B).
(23)
If AB is not full rank, then mmnn ( (AB) swin ( (A) (A)mmin ( = 0.
Lemma 8. (Von Neumann's Trace Inequality (Von Neumann 1937)) Given two n x complex
matrices A, B, with singular vales a₁ 2 ... 2 On and bj 2 ... bn respectively. We have,
Tr(AB) S asbi
This is classic result whose proof we exclude.
As direct consequence of Lemma g [r((AB] S na,bi.
C.2 POSTERIOR ESTIMATE
For reference, we reproduce the posterior estimate for the true parameters 0 As a shorthand, we write Y1-++1 (y1...., 1)))
p(T(YIM) -N(rr Erprine:
(24)
Σ-1 YYM =Σ (oaxix] +ofl)- Xi,
(25)
M
PT|YN: Er|rr.s
x (oxx, + +ofl) Σ
(26)
p(0M+1 YLM. = -N EemenlYisen
(27)
Eatr = o,T+ Σ E
(28)
E-1
1 X M Eg-TY
(29)
| Eo M X + E-1
X
(30)
20

---

Published as a conference paper at ICLR 2021
C.3 UPPER BOUND FOR META LINEAR REGRESSION
In this section we prove the main upper bound result of our paper, Theorem 4
Theorem 4 (Meta Linear Regression Upper Bound), Lei OM41 be the maximum-arpossteriori estima- tor, |0 Then,
RPLR S sup 0 (B2))
ElllOn+1 0M++ll3] (( DD,,)
where,
Mn
Mn
C(M,n,k) =
and, D(M, n, k))
n(M+x))
+ A1)
Mn La
+ A2)
Expectations are taken over the data conditioned 0 Oas+1 Additional terms not depending on d, M, n, are defined in Appendix C.2
Before proceeding with the proof, we introduce some additional notation and technical results.
Additional notation quantities.
To alleviate (only little of) the notational clutter, we will define the following
Σ E
2 Eotr YIM
min (X/VT) = =1
Smin (XM+1/X4// /Vk) 82
8max (X/vi) 711 -881
maax (XM+1/VR 7/2 KM+182
= =f/00
Q2 = 2 /08
L [M [M+K*)s 382
L of
L 203
02
saa
A
A
A2
As we have uniform bounds on the singular values of design matrices, we introduced an auxillary matrix X whose largest and smallest singular values given by vnca and vnss respectively.
We will also write S(A) = Cov[A, A], and x(A) Smax (A)) Smin (a) throughout.
Bias- Variance Decomposition of the estimator:
is standard, decompose the risk into the bias and variance
0 M+1
M 2| [[ (0 0M 0M441) T)
(31)
= =T - ( Tl)
(32)
O 0 + Tr(E[((M+1 - 0M4)))1((0
0
(33)
In the sections, will derive upper bounds the bias and variance terms above.
21

---

Published as a conference paper at ICLR 2021
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 (Variance decomposition) Let 0M+1 10M-i1Yaas as defined above. Then the variance of the estimator can be written as
Tr(S((M+1)) =
Proof.
TM(CoN(0++1,0m1
(34)
- 8(E'2% Mr(MEN))
(35)
=
S(C'2%
PT|Vi:M
))
(36)
(37)
We will now work towards a bound for each of the two variance terms in Lemma separately. To do so, we will need produce bounds on the singular values of terms appearing in Lemma
We begin with the covariance term Σ'
Lemma 10. (Novel task covariance singular value bound) Let L, A and be defined above. Then,
8 8max
(E)
M++1 82
h:
Mn
71
A
Proof.
Using Lemma 6 we can bound m (2') follows,
Smax
Σ'
mmax (EosetilM
(38)
S Smax (10 2 X
M+1 M41XX411 + Σ-1 Sptritinn )
(39)
1 1/8min (a XT
M+1 M+1 XM+1 + h-1
(40)
< 1/ (o X M+1) + 8min 200t))Yno))
(41)
1/(smiu (o M+ X M 1/ max ( (Eo+r(Hi,s))
(42)
Now, using the auxillary matrix X,
mmax (') <
Smin (a x 1T Xx+11)
(43)
o + M Smax (XXC--1X)-1
Smin (X XM+1XXMD
(44)
0 M emin (X E-1X)
1: 2(MM41/VB)
(45)
2
0 smin (X TTCTC (-1X)
182
(46)
M+1
o + M smin (X (XT (XogiX +021) 1X)
22

---

Published as a conference paper at ICLR 2021
Above have used Lemma repeatedly. alongside the standard identity, Smax We continue now, additionally using Lemma
(A-1) Smax(A
Smin Smin(() (A)
k8
Smax
(47)
MM+
0g + M (X X) 8]mmi (XooiX +o (1)1)
ks
(48)
MM+1
0g Smax (Xo11X++of]
Awin (X X)
(49)
0 GM
0 +
smax (X bt0
n2
ks
(50)
RMr+
Smiax (XX (XX))-0 ns9
0 +
ks
(51)
OM+1
og +
0 n8g
Mn
OM+1 M+1
ks
(52)
8f02
2
M+1
(53)
8
Mn
A
L
Next, we deal with terms appearing corresponding the data from the source tasks.
Lemma 11. (Source tasks covariance singular value bound) Let Õr = xxx + ofT, and write R x(Ci) and K, m(E+|Vrss)) Then,
Smax 2 (E ( Er Viia
D1
2Mozus? + K2 (1))rr
and,
1
mmxx (oi <
=: D2
ns
Proof.
Using Lemma 6 and Lemma 7 we have,
Smax 2E Ey Yeiss)
= Smax
2 "1Eg)
8+ YEM Erprisse)
(54)
S 8max
(52 Yaaa )max 2 2 (Yina)
(55)
Smiu
-2 2(E Miias )mmax (E.a)
(56)
Smin
-2 22 + ErTYiiis )max 2 2 (E.M))
(57)
Smax (Er(yi.ne)
(58)
(03 + smin (2i//rrnr)) )
23

---

Published as a conference paper at ICLR 2021
Now, using oj 0,
mmax (Erprrn))
mmax (Er)Yi )2
S
(59)
0 + Smin (2r (2rr) )}2
2 min ( + Smiu (2i VV )
(60)
2g
Praax
2 Ke
x2
Introducing the auxillary matrix X and using Lemma and Lemma on ETpriN we have
(61)
20 Smaxx (Zir) Vi.as
2M mii (XTC-1X)
where,
Smin (X X)
Smin (iin(XTer (XT x) 2
(62)
Mmax ((1)
n.s
(63)
8max (C1)
This gives the first stated inequality,
8max 2 2E (207/1 Dr Yumd S 2Mo + 1
=: D
(64)
$m)x(C1)
K
The second follows as.
of
Smax (of = Smin (oxXX +of1)
(65)
of
(66)
Suin xxxXT)
Smin (0
of
(67)
ns of
D2
(68)
nsi +1
In Lemma 11 we introduced additional condition numbers, which we can bound as follows,
R = xCx( = xxxxxXT T +ofl)
< x(o]xx s x(o]xxX (n(O))) = =x²,
(69)
K, x(E+pprre) I n(X ()x(()) = R A.
(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(0 < K ns+1 2 k
Mn
d
+
$2
n
L.
Li
R
+
A1)
Me
La
+ Az)
Proof.
First, by Lemma 9 we can decompose the overall variance into two terms:
Tr(S( TrE'' + TY(S(EEE -1 ()))))))
X
We deal with the left term first.
24

---

Published as a conference paper at ICLR 2021
Using trace permutation invariance and the von Neumann trace inequality (Lemma 8). bound the left variance term as follows,
We can upper
XM ( X
(71)
S dka -2
M+1 M+1 mmax (E') 2
(XM+1//V /Vk)
(72)
dko 2
M41 maxx 22)
(73)
For the second variance term, we observe that,
Tr(E'E/ S S 10 "E')
(74)
M Σ
= =TrE'' -1 S(E, \YMM
( + - 'EE
(75)
S MTr(''s E -MIMIN X (C-1 Xx, Yim I0 E`)
(76)
= MIT(E''2 -1 E X 09 X 2 2n)
(77)
I Msmax (E')² smax 2 (E Vi:
E Tx C
(78)
Using Lemma
we have,
Tr(E'' -1 - )( Σ') S Smax
Dr X x)mmux(( (TT))
(79)
s Smax
( MD min(n, d)nsmax (ÔT))
(80)
M min(n, dyn
Smax (E)) D2 2Mo (C1)
(81)
+ (m))(C))
Smax (G)
M Mmin(n,d))
S Smax ( D2
(82)
2M Mooussssmn (C1)
o7
+
(max(Cr)
x²
min(n, d)n
M
Smax 2 D2
(83)
OM
2Mn
+
01
RR.
"2o 02
5max (27)2
nd
M
(84)
M+1
nof
+
RK- 02
2M
K2 K2aa
Finally, rearranging and using Lemma 10 follows,
we can bound the sum of the two terms in the variance as
Ir(S(OM+1)) S Smax (E')2
nd
M
(85)
ns 0n
2Ma
+
KN-022
Smax (2')2
2333233211111
nd
M
(ke 7 + 2
020+1
2M 1111
M+1
RM,02
+
(86)
2 1 0 M+1
k + n2
(87)
+ A
Mnd
kd
(88)
2 2 )
2Mnazu3r41
0n 018381441
AN-002
N M++1 M+1
22
Mn
d
4: +
k +
(89)
I
+ A
L
+
A )
Mn
L
A22)
25

---

Published as a conference paper at ICLR 2021
C.3.3 BOUNDING THE BIAS
Lemma 13. (Bias upper bound) Given 0 ......, 0M.1 B2(1), we have,
Mn
[[(0++1 [0++ d k n(M++*)as
02
Proof. The bias can be computed as follows,
[ [0(0++1 0ws+1)] = E: - O
(90)
E0utr Marei B(o 192 + E (
Mr(2sM Mo 0M1+1
(91)
Dou MM (M X MM41 1 + E-1
14t//ii B
0
0
(92)
= XM + Σ-1
20 ).
(93)
(0M41 X M41 X + E-1 2+ Butsyrins)
- 0+
(94)
(F+ G)- +1 GpT)PN))) MM+1
(95)
GF+ (F (F+ (F G)0M+1+++++++00 (F |Y:M
(96)
+ G 0M+1),
(97)
where we wrote F = T M- X and G = 1==>i--ryyaa 2/ Thus,
0
El00x+1 0m+1)] B[(0 - O M-) < [1 G)
00++1l
We can bound each term in turn. First, note that |G]| < 1/0 and we have bounded [(F - G) above. We can write,
Bpapysa 0M+1l13-
00M+1
1=1
Bpppai 0M41112-
E
X. CT x10%
Ey Viss Mi
7 0M+1
i=1
X. Oj Xi(0: -Oart
E ViA |I,,T 1x(00 0M++1)l
Σ p2, YuM lla ||, Xx11a
The last line follows from the fact that the parameters lie in ball of unit radius. We now proceed by bounding the sum by M times the supremum - with some light abuse of notation,
||p 0041113 12 < (S (X (TTŌ-11 xxT--xX)smse x xxC-xx))²
5 max (X (TT--X) O(1)
Thus, overall the convergence of the bias is bounded by,
Mn A(M+*?)a
B[(@ 0) (E( 0M++)) < O S (E'?) 50 d
k
+
+ A
26

---

Published as a conference paper at ICLR 2021
The proof of Theorem 4 is given by the combination of Lemma 12 and Lemma variance decomposition of the risk.
13
and the bias-
D ADDITIONAL EXPERIMENT DETAILS
D.1 HIBRARCHICAL BAYES EVALUATION
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 x², for = 0, d in each row of X
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++ values. The 0 values were sampled once from the hierarchical model with 7 = [0, 1, 2, 0, 0, 3, 1]. and of 0.1
Code to reproduce these plots is provided in the supplementary materials with our submission.
D.2 SINUSOID REGRESSION WITH MAML
Hyper parameters
Description
noise at test time.
M
number of tasks at the training tasks
Mg
number of tasks at the testing tasks
eps-per_batch
episode per batch
train_amp aainaampl_anggee
range of amplitude at training
train trainephase-ii range val ampl range val phase range inner_steps
range of phase at training
range of amplitude at testing
range of phase at testing number of steps of Maml learning rate used to optimize parameter the model used to optimize parameter of the meta-learner number datapoints at training tasks(support set) number of datapoints at testing tasks (support set) number datapoints at training tasks (query set). number of datapoints at testing tasks (query set).
inner
meta.Ir
n
k
ng
liq
For all of these experiments we used fully connected network with layers and 40 hidden units per layer. The network 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 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 gpu and cpus. This experiment therefore lasted 20 hours in total.
M 50, E [20, 200), E {100, 1000}, E [10-8 1.5), Mg 100, eps_per batch 25, train_an aain_amml_range [3, 5]. val hal__hase_raaa range = [0, π x/2], inner_ 5, inner Ir = 10-3 meta Ir = 10
[1,4] 4), train train_phase__ame phase_range
[0. π 1/22, val val_ampl_range
27


Reviews:
[{"review_id": "oDGTbYa2kkM", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall I feel this paper study an important problem of the meta-learning and the derivation all looks correct. The main drawback is that the presented minimax lower bound is quite pessimistic that may not fully exploit the potential task similarity in practice, but I feel it is still acceptable to first study the minimax lower bound, and leave the case with more structure as future work.\n\nI would like to ask if there is a gap between the description at the beginning of Section 5 and the analysis starting from Section 5.1, as the bayesian model described at the beginning of Section 5 does not assume theta have ell_2 norm smaller or equal than 1, and in fact, cannot be universally hold as theta is sampled from a d dimensional Gaussian (can have high probability arguments instead). However, the analysis throughout Section 5 all have this constraint. I don’t see strong dependency on the norm of theta (e.g. in the covering number, KL bound etc) but I hope the authors check and clarify it in the next version.\n\nOne small tip: lower bound is better represented via big-Omega notation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fucdd0klKwK", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Pros: \n1 - The paper seems to be well written, have a good review of the references and necessaries for understanding the problem. \n2 - Some of the results found in the paper seem to be interesting. For instance, the asymptotic analysis provided in paper gives some insight on the performance of meta learning algorithms with the number shots, ratio of observation noise to the sampling noise and the number of tasks. \n\nCons:\n1 - It seems that most of the results of the paper are based on Loh (2017). It is expected that the author differentiate their contributions  with those of that reference more clearly. \n2 - Some of the notations are misleading. This is a minor issue and up to the authors to change it or not but it may help with the readability of the paper. Some notations like $\\theta$ are usually used for parameters in models. In this paper, $\\theta$ is used as a function. I understand why the authors decided to use it as a function but it may be a bit misleading. \n3 - Some of the assumptions in the paper can be very restrictive. For instance, it is assumed that the distributions are $2\\delta$-separated while close in the KL divergence sense. Isn't this too restrictive? Maybe it is good for the authors to try to talk more about the implications of such assumptions. How does this restrict the space of interested probability distributions? \n4 - Another example of a restrictive assumption is bounded minimum singular values. How does such a restriction affect the space of considered solutions? \n5 - There has been no effort in comparing with any bounds that are available currently. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "cx0hSiwEVhj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nMy major concern is that in theorem 3, $Mn$ needs to grow exponentially with $d$ to be significantly better than the case when there are no training tasks available (theorem 2). However, theorem 4 states that $Mn$ just needs to depend polynomially on the dimension $d$. Hence, the upper bound and the lower bound on the risk have a gap on the parameter $d$. Thus, it is not clear if the lower bound in Theorem 1 is tight. It would be great to have a discussion on this and the assumptions that one needs to take to improve upon this gap. \n\nFew other concerns:\n1. In the hierarchical regression setting, the assumptions for theorem 3 and theorem 4 are different. A discussion on how the lower bounds will change, if we assume different variance of task parameters $\\sigma_{\\theta_1}, \\cdots, \\sigma_{\\theta_{M+1}}$ and task-specific observed samples $\\sigma_1, \\cdots, \\sigma_{M+1}$, will be helpful.\n2.  The proof of theorem 3 focuses on packing the parameter space $\\theta$ by an $\\epsilon$-net on $B_2(4\\delta)$, where $\\delta$ is fixed later on. However, the model assumes $\\theta$ coming from ball $B_2(1)$. There seems to be some mismatch in the theorem statement and the proof.   \n3. The risk in theorem 4 involves few more parameters whose effect on the risk hasn't been checked in experiments e.g. the ratio of variance in observed samples of novel task v/s variance in task parameters. Also, it will be interesting to see how the results change when the data distribution is changed since the risk depends on the singular values of the data matrix. \n\nI have read the proofs. They are easy to read and understand. My scores are slightly on the lower side because I am concerned about the tightness of the lower bound in Theorem 1. I am happy to discuss this with the authors and other reviewers during the discussion period.\n\n**After Rebuttal**\nI have read the reviews of other reviewers and the responses of the authors to the questions posed by the reviewers and Ahmad Beirami. I understand that the authors have taken a pessimistic approach to compute the lower bounds of risk in the minimax setup of meta-learning. However, I believe the paper is an important step in this direction. Theorem 3 and Theorem 4 are important additions to the paper, which show a margin between the pessimistic lower bound of the risk and the actual risk with the introduction of structure to the learning setup. Overall,  I enjoyed reading the paper, and I have increased my score after the rebuttal.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AW3G8IwWU9U", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the performance of a meta-learner theoretically in two settings. In the first one the overall number of possible tasks is limited and tasks are close in KL-divergence. The second setting is MAP estimation for a family of linear regression tasks. Lower and upper bounds are provided on minimax parameter estimation error.\n\nThe bounds solidify common sense knowledge about the role of the number of training tasks, number of samples, and task relatedness and diversity on the performance of meta-learner and are supported by numerical examples. I am in favor of accepting this paper. I'll provide suggestions for improving presentation.\n\n1. The assumption in the first setting is that the tasks are close in distribution space but far away in parameter space. Could you mention some examples of such set of tasks? It does not seem like a weak assumption to me, as mentioned in the paper, but then this is the nature of lower bounds. The point is not to model a typical scenario but to design hard cases that lead to high error. But in any way an example is necessary to show that this situation is possible.\n\n2. It seems to me that the lower bound in the first setting has less to do with the performance of the meta-learner than suitability of parameter estimation error as a measure of performance. At the end of the day, it is accurate predictions, and not accurate parameters, that matter. The setting is designed so that tasks have similar distributions but quite different optimal parameters, which results in a high parameter estimation error for the meta-learner. It could be that the meta-learner in fact makes quite accurate predictions (since the tasks are actually close in distribution space) despite its high parameter error.\n\n3. The first setting is worded generally (novel task generalization) while the second setting is presented as a more specific scenario (hierarchical Bayesian linear regression). The first time I was reading the paper I assumed that the first part describes general results on meta-learning and the second part shows a particular instance of the previous section, which was confusing as the second setting does not satisfy the assumptions in the first setting. I suggest presenting these two sections as two particular and different settings as they are.\n\nMinor comments:\n\n1. The statement of Theorem 1 has undefined notation. I assume I(.;.) is mutual information but it is not defined. The text defines W|\\pi and Z|\\pi but the equation uses \\pi_{M+1} and W and Z separately. What do \\pi_{M+1}, W, and Z (without the vertical bar) mean?\n\n2. The paragraph above Corollary 1 is hard to understand. Do \"training task\" and \"meta-training task\" have the same meaning? Also, if the number of previous tasks is M \\leq J-1, how can there be J previous tasks that are close?\n\n3. What is B_2(1) in 5.1?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study the theoretical performance of a meta-learning in two settings. In the first one the overall number of possible tasks is limited and tasks are close in KL-divergence. The second setting is MAP estimation (in a hierarchical Bayesian framework) for a family of linear regression tasks. Lower and upper bounds are provided on minimax parameter estimation error.
This paper has spurred a lot of discussion among reviewers and (competent) external commentators. Most of these criticisms were right on target, but the authors managed to convince the reviewers and myself that there was simply an issue of presentation of the main results. I suggest the authors to take into serious considerations all the aspects raised by the reviewers that has generated misinterpretations of the presented results.
Decision: Accept (Poster)