Task Relatedness-Based Generalization Bounds for Meta Learning
Authors: Jiechao Guan
Zhiwu Lu
Venue: ICLR 2022 Spotlight (2022)

Abstract: Supposing the $n$ training tasks and the new task are sampled from the same environment, traditional meta learning theory derives an error bound on the expected loss over the new task in terms of the empirical training loss, uniformly over the set of all hypothesis spaces. However, there is still little research on how the relatedness of these tasks can affect the full utilization of all $mn$ training data (with $m$ examples per task). In this paper, we propose to address this problem by defining a new notion of task relatedness according to the existence of the bijective transformation between two tasks. A novel generalization bound of $\mathcal{O}(\frac{1}{\sqrt{mn}})$ for meta learning is thus derived by exploiting the proposed task relatedness. Moreover, when investigating a special branch of meta learning that involves representation learning with deep neural networks, we establish spectrally-normalized bounds for both classification and regression problems. Finally, we demonstrate that the relatedness requirement between two tasks is satisfied when the sample space possesses the completeness and separability properties, validating the rationality and applicability of our proposed task-relatedness measure.

Published as a conference paper at ICLR 2022
TASK RELATEDNESS-BASER BOUNDS FOR META LEARNING
GENERALIZATION
Jiechao Guan
School of Information, Renmin University of China, Beijing, China 201 w0.2000990ruu..... edu.cr
Zhiwu Lu"
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China luzhi i wuê ruc. edu.cn
ABSTRACT
Supposing the n training tasks and the new task are sampled from the same envi- ronment, traditional meta learning theory derives an error bound on the expected loss over the new task in terms of the empirical training loss, uniformly over the set of all hypothesis spaces. However, there is still little research on how the relat- edness of these tasks can affect the full utilization of mn training data (with m examples per task). In this paper, propose to address this problem by defining a new notion of task relatedness according to the existence the bijective trans- formation between two tasks. A novel generalization bound of O mm for meta learning is thus derived by exploiting the proposed task relatedness. Moreover, when investigating a special branch of meta learning that involves representation learning with deep neural networks, we establish ppectrallynnormalinn for both classification and regression problems. Finally, we demonstrate that the relatedness requirement between two tasks is satisfied when the sample space pos- sesses the completeness and separability properties, validating the rationality and applicability of our proposed task mesktrelatedness measure.
bounds
INTRODUCTION
By leveraging knowledge distilled from the training task&] meta learning (Thrun Praut 1998
Baxter] (0000 learns to perform well on a new but related task. One important branch of meta learning achieving great success in practical machine learning applications is representation learning Krizhevsky et al. 2012] Bengio et al. 20133 He et al.) 2016), where one first learns a shared feature extractor (c.g.. deep neural networks) over the training tasks, and then learns a prediction function for the new task on the top of the features constructed from the extractor, within few gradient steps (Finn et al., 2017, Li et al. 2017) or with a feedforward process (Snell al.) 2017 Sung et al.) 2018) If the feature extractor can capture the common information across tasks, it is possible that utilizing representation learning can help learners generalize well to a new task with much less data.
To build up a rigorous framework to support this intuition, the pioneering meta learning theory as- sumes that both the n training tasks and the new task are i.i.d. generated from the same environment (Baxter 2000). Then, analogous to the single task learning whose goal is to select from the hypoth- esis space H. a hypothesis h to achieve the minimal expected loss on the task, meta learning expects to choose from the hypothesis space family H hypothesis space H(E H) that contains good solu- tion to any task sampled from the environment. Under the PAC learning framework (Valiant 1984
Vapnik 1989), (Baxter 2000 derives a uniform bound of O(V of hypothesis space H. over the new task in the environment, according the empirical loss of H
C
Ca on the expected loss
"Corresponding author.
In this work, task represents data distrihution, say probability measure the sample space.

---

Published as a conference paper at ICLR 2022
over the n training tasks, where C1 C2 are different logarithms of the covering number (Anthony & Bartlett 2002) about H. However, compared with the single task learning whose error bound m ( of any h E H can utilize all m training samples, where C' represents certain complexity indicators such as the VC-dimension (Blumer et al. 1989) or the entropy (Pollard 1984) of H. Bax- ter's 's meta learning generalization bound of any H E Hi cannot fully utilize all mn training samples (e.g., with bound of O Vum ) without extra terms of O
Vn or O( vm )). Nevertheless, there is
still little theoretical research on how the relatedness of these tasks can affect the full utilization of all mn training data in meta learning under Baxter's proposed i.i.d. task environmetn framework.
In this paper, we propose to address this problem by studying the task relatedness and provide a new generalization bound. To achieve full utilization of all training sample, our motivation is that differ- ent tasks need to be 'related' enough such that samples from various measures can be assumed to be generated from an 'almost' identical distribution. The equivalence relation of different data distribu- isomorphism of their induced measure space
tions actually corresponds to the meeasure-preservig (see Definition 7 Therefore in this paper, we define a new notion of task relatedness called almost bijective transfor-
IT-relatedness in Definition 3 according to the existence of a measure-preserviie mation between two measure spaces associated with different tasks. A PAC-style generalization error bound that fully utilize all training data is thus provided in Theorem 3 by exploiting the pro- posed task relatedness. We further employ this task relatedness notation analyze the representation learning with deep neural networks, and establish non- can---arrmte---oo conteer--ouuutbbbeddd spectrally spectrally-normaaiza normalized bounds for both classification and regression problems under the meta learning framework. Finally, we demonstrate the rationality of our proposed mask-relatedness notion from theoretical standpoint.
Our main contributions are summarized as follows:
(1) We propose a new notion of task relatedness, called almost Il-relaeddness, by exploring the existence of a bijective transformation between two tasks in the environment. A novel PAC-style
generalization error bound of Oly C.) is thus derived for general meta learning by exploiting the proposed task relatedness, where C' captures the logarithm of the covering number of a hypothesis space family. Such bound thus can fully utilize the whole n m training data in meta learning.
(2) For meta learning that involves representation learning, we bound the covering number in Con- tribution (1) with two covering numbers that are both defined over single task, making our results suitable to be combined with recent works of deep neural network in the single task learning. In
particular, we provide the spectrally
bounds of O(1
Ci+nC2) for classification and re- 7L972
gression problems in meta learning, where C1, C2 are certain complexities that are dependent on the matrix norms, but independent of the total number of the parameters, in deep neural networks.
(3) We rigorously demonstrate that, any two tasks are almost TI-rllaed if the sample space is a com- plete separable metric space, validating the applicability of our proposed task-relatedness measure.
2 RELATED WORK
Meta Learning Theory. The first theoretical analysis for meta learning is performed by (Baxter 2000). which gives a bound on the expected loss on the unseen task of any hypothesis space in terms of the empirical training loss. Under this framework, (Pentina & Ben-David 2015) studies the generalization error bound of the hypothesis space in the case of kernel learning. Although many follow-up works also assume that all tasks are sampled from the same environment, they bound dif- ferent kinds of generalization error from various perspectives. One important branch is to bound the transfer risk over the new task of a deterministic procedure, such as the linear feature transformation algorithm (Maurer 2009) and the Baves algorithm in PAC-Bayes theory (Pentina & Lampert 2014 Amit & Meir 2018). Among them, (Chen et al. 2020) derive a bound of O / ) from the algorithm
stability perspective, and (Pentina & Lampert 2014) derives a bound of O V + / (wee suppress the complexity factor in the numerator for concision, similarly hereinafter). Another branch aims to bound the excess risk of the task specific function returned by ERM algorithm over the unseen task. They study meta learning theory from different views, such as multitask representation learning
?A measure space is triple (7.A, P), where 7 is the set, A is the o-algebra on Z, is measure A.
2

---

Published as a conference paper at ICLR 2022
[Maurer et al., 2016) and online learning (Khodak et al., 2019). Among them, (Du et al. 2021 and Tripuraneni et al. 2020) escape from Baxter's 's proposed task environment setting, by defining task similarity or task diversity notion, obtaining similar excess risk bounds of O ymm v in the case of ditheeinnnsion transfer learning. Our work follows Baxter's s proposed i...d task environment framework, and gives an improved bound on the generalization error of the hypothesis space. The detailed comparisons between our results and that in (Baxter 2000) are presented in Appendix [C.
Task Relatedness. Another related work (Ben-David & Schuller 2003) also proposes a task- relatedness concept, by defining the bijective transformation æ on the input space X. But in our work, the bijective transformation is imposed on the sample space Z = X Y (where Y is the output space). It is not difficult to see that the task relatedness considered in (Ben-David & Schuller, 2003) is actually special case of our defined task-relatedness measure. We further validate the rationality of our proposed notion by revealing the existence of the bijective transformation и on Z when Z complete separable metric space, making our results more applicable. The differ- ences between our proposed task-relatedness notion and that in (Ben-David & Schuller (2033) can be found in Appendix C.2 Besides, (Khodak et al. 2019) and (Du et al.) 2021) also consider task- relatedness notions such as parameter-closeness or sharing low-rank subspace for meta learning. To distinguish the notions proposed in this paper with others is truly one of our future directions.
3 PRELIMINARY
In this paper. we use uppercase letters (e.g., Z) to represent different spaces. The boldface z repre- sents matrix, with z; as its i-th row and 2,j its j-th column. denotes a vector. All detailed proofs of our theoretical results are deferred to the Appendix B for reader's benefits.
3.1 META LEARNING
The formulation of meta learning problem can be summarized as follows. We are given sample space Z = X x Y, where X is an input space and Y an output space. In this paper, we assume that Z is a complete separable metric space. A loss function is defined as Y X - IR and we assume that has the range [0, 1J. or equivalently, with rescaling technique, we assume that 1 is bounded. An environment (P, Q) is two-tuple, where P is the set of all probability measures' ddittiibutions/ tasks on X x Y and Q is a probability measure on P. A hypothesis space family is formulated as IHI {H), where each H. E H is a set of hypotheses's functions h X + Y. In single task learning, the learner needs to choose an optimal hypothesis ht* E H. to minimize the expected loss of h over probability measure P(E 'P) on the product space X x Y: er = Sxxx 1(h(z), y)d y). Similarly, the goal of meta learning is to find a hypothesis space H E H which contains a good solution to any task sampled from the environment, and minimize the following expected loss of H over a measure Q on P (Baxter 2000. (6) erq (H() = Jp inf er p (dQ())))PPPP)))))) In practice, it is hard to minimize (H) directly since we do not know the exact distribution of the environment measure Q We can only capture the information about the environment (P, Q) by observing the training data z generated from the n training tasks Pj(j = 1....,)) n) that are i.i.d. sampled from the environment measure Q. Formally, this is achieved in the following manner: (1) Sample times
from P according to Q to generate (i.i.d) probability measures Pt, PI,..., Pn. (2) Sample m times from X x Y according to P3 to generate [(11) vi.):..., (fimjj Mmm)) (1 < j & n). (3) Denote 2, = (Igz Mkg) Z, and an (m, n)-sample will be generated, denoted by z and written as matrix z (zzy mmn- We then choose to minimize the empirical loss eř, over the training data z for meta learning, which is defined er*(H) En infnew eña,, (h), where 2 the j-th column of matrix z. Let P = (Pı,.., Pn). We also consider the following loss err(H) as the empirical estimate of the expected loss enq (H)): érp = ΣE= infNEH err, (h).
Definition 1 (Baxter 2000 For any hypothesis h X + Y, define by as the composition of loss function and hypothesis: hu : X x Y + [0. 1] by hi(x, y) = 1(h(x),v) v). For any hy- pothesis space H. E H. define Hi = {hi : h E H} as the function space on Z. For any sequence of n hypothesises (h1, h.)) define (Ir...., (h))
(X x Y)" - [0, 1) by We will use by to denote "o1,...,,,))
(hi,..,, hn ( yi,... Ins ya) = =1/n Ex,1(h,(2r
VH E TH, define HT = [(he,... h1 by,.., hn E H} and Hy = Uner Hp.. Define P(h)) = Sxxx hi(x, v)dP(z, v) and P(H)) = infmee P(hi) where P is a probability measure on 7,, and we have P(hi) (1) and (H) = P(Hi).
3

---

Published as a conference paper at ICLR 2022
Definition 2 Let (M, d) be pseudo-metric space. Ye > O, a subset T is called c-cover of T S M if vt E T. Et' E T such that d(t, 1¹) S Let P P1 x... x P. be the product measure on Z For any (HI }) b Zn + [0, 1], define the pseudo-metric dp (hv, h)) = Sz [b)( (())). Then for any E > O, the covering number (e, Hil dp) is defined as min[[7]] is an e-cover of H under the dp pseullometric), where (T) is the cardinality ofT.
We hope to use the empirical loss (H) or érp (H) to approximate the expected loss erq(H) Instead of the traditional absolute value function d x. y) = |ar yl we consider the following metric |x-al to measure the distance between æ and y, which is x+++
function (I/ > 0, 2 0) dy [a. 3]
first used by (Haussler 1992). In Section 4 we will bound the deviation dz (H), ere by bounding d ()() (rp and d (1), (H)),, respectively.
3.2 ALMOST II-RELATED TASKS
In this section, we first propose new concept of task relatedness, which is called almost II- relatedness. This notion can be considered as the extension of the 'II-relatedness' notion proposed by (Ben-Dare David & Schuller, 2003). The distinctions between our proposed task relatedness notion and that of Ben-BenDai & Schuller (2003) can be found in Section C.2 of Appendix
Definition 3 (Almost TI-Related Tasks) Let IT be set of transformations π 7 - 7. and let P, Pi be probability measures on Z, = X x Y. We say that P, Pi are almost IT-related probability measures's tasks, if the following conditions are satisfied: (1) MN,,, N1 C '6 such that P(N)= P = O, and
(2) 3क II, is one-to-one mapping from (Z\N, P) onto (Z). YA S ZAN,A is P- (T(
measurable if and only if i()((A (TT))) v) (a, v) E A) (ZAN)) is Pi-measurable, and (3) J2YN IAdP= S2 I,(aydP,, where 1 is the indicator function on the set A, and
(4) the image T (N) is a P.-measurable set, and the inverse image x (N₂) is a P-measurable set.
Note that condition (4) is a weak requirement only to ensure the measurability as well as the integra- bility of the mapping π (or -> on the measure zero set N (or N1). Actually, to validate whether two tasks (say P and P1 ) are almost I1-related, the most important step is to find the bijective transformation æ which satisfies the listed conditions (1)-(3 in Definition 3 Then, we can extend the transformation π to the measure zero set N by defining IT (NN as a P: P--muauura set (e.g. a Pı-measure zero set) and extend - to Nj in a similar way, such that the extended transformation satisfies the condition (4). The existence of such transformation between two tasks can be theoreti- cally guaranteed by some general topological properties of the given sample space Z, which will be discussed in detail in Section 4.4 We next give closure property assumption of the space Hi E Hi when the transformation set II is imposed on H₁. Similar to (Ben-David & Schuller 2003) which assumes the closure property of any hypothesis space under the transformation I1, we also assume that the closure condition is satisfied by any H4 E HI, for deriving better generalization bound.
Definition 4 Let II be the set of transformations on the complete separable metric space Z = X x Y. We say that the function space H4 is closed under the transformations of II, if for any hy E Hi, any ι E II, we have the composition function hyOT E Hi-
We need to give more explanations to the rationality of the closure property of the function space Hi, as the closure property is a very important assumption to derive our generalization bounds. Actually, the almost I1-relatedness defined in Definition 3 can induce an equivalence relationship between two tasks, according to the existence of one bijective function π E II. The function π can also induce an equivalence relationship between two functions in the space H4. That means, if function space Hi contains a good solution to one task P. then H4 should also contain a good solution to the almost II-relaedd task P1 of P. Since the two tasks P and P1 are equivalent to some extent, the function space Hi should simultaneously contain the good solutions to these two similar tasks. With such closure property assumption, the complexity of the function space H; is related the degree of relatedness between different tasks from the environment. If the tasks in the environment are all similar (e.g., almost I-related), then it is sufficient for Hi to contain one good function well as its
AA mseudo-metric is metric without the condition that d(z, y) ==
4

---

Published as a conference paper at ICLR 2022
II-related variants to generalize well to all tasks. Such closure property assumption of the function space is also considered in Ben--avvi & Schuller (2003). They have demonstrated that as long as the function space is rich enough to contain some function well as its equivalent class, then the closure property assumption can be fulfilled. Thus in this work we assume such basic closure assumption of function space Hi holds derive novel theoretical insights for meta-learning
We introduce another concept induced from the r-related tasks, called almost II-related environ- ment, and its theoretical properties, which will be used derive our theoretical analysis in Section
Definition 5 (Almost I-reeattdd Environment) In meta learning set up, environment (P: Q) on X Y is called an almost ll-related environment, if there exists a common probability measure P on X x Y, such that for any measures P. E P(i I,I is the index set), P and P. are almost II-related in the sense of Definition 3
Lemma Let (P.Q) be an almost Il-related environment on X X Y. Hi a function space on X x Y. Let P be the underlying common distribution as defined in Definition 5 and N be the P-measure zero set as defined in Definition 3 Then for any P-measurable set
Z N,N,oo any P. E P(i E h) E H4. we have P(A) = P.(TT( P. P.(hes, P(h)), where n, is the
corresponding transformation between II-related tasks P and P, (as defined in Definition 3
Lemma 2
Let (P, be an almost II-related environment on X XxY, P be the common distribution that is almost I--reaatd to any distribution from P. If function space Hi (on X x Y) is closed under the transformations of II, then for any probability measure P. E.P, eTp = erp, (H).
We provide two insights into the theoretical result in Lemma to further explain the motivation of our proposed task relatedness notion: (1) To fully utilize all training samples, two different tasks need to be similar enough so that the hypothesis space which performs well on one of these two tasks can also perform well another. In other words, the 'best' performance of the hypothesis space need to be similar in both tasks, which is the result in above lemma. (2) To achieve the goal in (1), the hypothesis need be large enough to contain good solutions that are invariant to the trans- formation between different tasks. Hence, insight (1) motivates us to define the Il-relatedness notion measure the similarity between two tasks in Definition 3 and insight (2) motivates us to assume the closeness property assumption of the hypothesis space in Definition 4 More explanations for
the motivation of our proposed task relatedness concept can be found Appendix A
THEORETICAL RESULTS
We first give novel generalization bound for meta learning in the almost Il-related environment in Section 4.1 This is particularly achieved by employing the theoretical properties of the almost Il-related environment in Lemma 2 As shown in Theorem 6 in Section 4.4 assuming the envi- romment to be almost II-related is reasonable when the sample space Z possesses the completeness and separability (which are general topological properties satisfied by many metric spaces). Sec- tion 4.2 derives a covering number bound for representation learning, which is an active area of meta learning. In Section 4.3] by bounding the covering number with the Lipschitz constants of the matrix and nonlinearity in each layer of the deep neural network, we further establish a spectrally- normalized bound that is independent Theorem 5 Moreover, we apply this theoretical result to analyze several practical scenarios like binary's multiclass classification and regression problems under the meta learning framework. The three main technical novelties of our work have been clarified in Remark 2 of Appendix the technical contributions of this work and outgoing research directions for meta-learning.
the number of the total parameters in neural network in
C to show
4.1 A COVERING NUMBER BOUND FOR META LEARNING IN ALMOST II-RELATED ENVIRONMENT
To bound (+)z(1) (7)) choose to bound the deviation d, (f)),rrp(ee)) and d de( (T))), respectively. We first give an explicit PAC-style generalization bound on d dr(erx (r) (H)), which can be considered as an inference of Theorem 18 in (Baxter 2000).
5

---

Published as a conference paper at ICLR 2022
Theorem He C H ......... .H Hi be the permissible class functions mapping (X Y)" into [O.1]. where Hi = {44 : E H. H. E HJ. @ means direct product. Let z be generated by m 2 2/(v²² independent trials from (X x Y)" according to the product measure P P1 x x Pr. For any v 0,0 < 1, for any H E Hi, with probability at least 1 - over 2, we have
8
dy (H), erp (H))
In vmnn
where z E 7(2mxn), the top half of z is actually z itself and the bottom half of z the copy of z. Vhr, hf E Hif;; (hi, h/) = 1/2m 2 [hr(2,) 1 -,;()));
On the other hand, we can actually bound the deviation dy (H)) (H)) as follow, by using the theoretical properties of the almost IT-related environment in Lemma
Theorem Let (P, Q) be an almost ll-related environment on the complete separable metric space Z = Y. Let P pm be generated by n independent trials from P according to some product probability measure Q". Then for any v > 0, any H E H., we have (1l)rp(H),,rr((f = 0.
we can obtain a novel generalization bound of conver- gence rate O /nm on (H) (H) that fully utilizes all mn training data under the proposed
Combining Theorem 1 and the Theorem 2
meta learning framework in [Baxter 2000). uniformly over the set of all hypothesis space H.
Theorem Let (P,Q) Q) be an almost T-related environment the complete separable metric space Z = X x Y. Let z be an (m, n) sample generated by the process described in Section 3.1 Let H (H} be any permissible hypothesis space family. Then for any H H. (0,1), with probability at least - 8 over 2, we have
4N Hf 64
jer z (7)) crQ(())
In
mn
8
Combining the above theorem and Lemma 2 we subsequently give a corollary which reveals the relationship between task-related meta learning setting and i.i.d. single task learning setting.
Corollary In the setting of Theorem 3 let Pa+1 be the new task sampled from the environment. Then for any H. H, (0, 1), with probability at least 1 1-6 over we have
64 mn
4N(c/4, Hy HH..d. dz)
er (H) S (+)
In
There two important points note about Corollary (1) If the hypothesis space H contains only one hypothesis and all probability measures in the en- vironment are the same, then the we can choose the bijective transformation between different distributions as the identity transformation, and the result in Corollary [ degrades to the traditional covering number based generalization bound in single task learning (see Chapter 10 in (Anthony & Bartleti 2002)), which utilizes all mn i.i.d. training data. In this sense, meta learning theory can be considered the extension of the conventional single task learning theory.
(2) When bounding the generalization error of hypothesis space H under Baxter's proposed meta learning framework, even though different tasks may have different distributions, we can still prop- erly estimate the expected loss on the new task according to the empirical loss on the training tasks, and fully leverage all ma (not necessarily i.i.d.) training data with the use assumed task related- ness in the environment. Actually, the relatedness condition can be satisfied by tasks that are focused on the complete separable sample space (see more explanations in Section 4.4).
4.2 COVERING NUMBER META LEARNING BOUNDS WITH REPRESENTATION LEARNING
In single-task learning setup, representation learning aims find a good feature embedding f F (e.g., deep neural network) which maps the input space X into the feature space V. A prediction
'Permissibility PPolladd 1984) is a weak measure-theore theoretic condition satisfied by almost all "roal-world" hypothesis space families. Without loss of generality, we assume that all hypothesis space families discussed through out this paper permissible.

---

Published as a conference paper at ICLR 2022
function g E G then projects the feature space V into the output space Y. Hence, the hypothesis space can be written as H. = Gaf. (f E F). Further, let Hi, = (Hz), each H4 = Gof. f E F, where 91 {gt ), 9t log is the composition function of the prediction function g and the loss function I. We will omit the subscript 1 of E Gi for simplicity where the context is clear. In meta learning setup, representation learning chooses to learn common feature embedding across n training tasks and learn n task-specific functions respectively for n. tasks, so we can denote the hypothesis space family HI {
+ Inaf 91..... 9n. E Gr, F} = {gi @ + g 91 ① ... ① In E 9 E F] = FF F. by defining F B (X x Y)n + (V x Y)" with f( y1...., Tn, Un) = (f(x), 81, f(xn): yn). We then define two sheudo-metrics over feature embedding space F and prediction function space 9i" respectively.
Definition 6 Vz- = (Zrz)2mxx E (22mxn), define the empirical measure P3 on Z which puts point mass 1/2m on each row Z, = I,..., 2m. Vs = ((((a))); Bij)) 2mxn = ((1is, ((vij,yis)) 2mxn' where f F, define an empirical measure Ps which puts mass 1/2m on each row 8, i 1,.., 2m.
V E F. define the pseudo- metric dir,.or(f.. (f.f) 1/2m Di=1 supgerr lgof(z.) go fz.)) and Vg, g' Gi, define the pseudo-metric d (9,99) 1/2m E (g(ss) g (s(s))).
2m
2m
Then the following two propositions bound the covering number of the hypothesis space family Hy with two covering numbers that are both defined over the single task.
Proposition 1 Let (P.Q) be an environment on V x Y. supp~@" pam N(c, 9I' dr.). Then for any e = 61 + cz. N(e1 62, HI, d2) S SN F.dip. (e2, 9i 2m).
Denote Nic, G 2m) = any E Z x we have
Let Ziz be the j-th column of the data matrix z. Let Vie,9i.20 = supp-psupa sup pam N(c, Gi, dr where dr.(g.g' g') = 1/2m Emm (((;)) - d(ss)), 4g.g E 9b 5= -S11,.... 82m). Then for any > O, we have N(c, d(p).or)) & maxigisn N(e, F, dp,,, and NN,, 9 2m)= S 2r,))".
Proposition 2
Recalling Theorem 3 and Propositions we can further establish the following covering number bound for meta learning with the representation learning.
Theorem 4 Let (P,Q) be an almost II-related environment the complete separable metric space Z = X x Y. Let = {HH be the set of hypothesis spaces of the form H = Gof. f f F.F Then for any H H. any 0 < E 1, with probability least 8 over z, we have
(etx( - erq (H))
64
In
+
64
max In 1515n
E F, Fi,,,,, + n nlnn E Gr, 2m))
We need to highlight the important role of Theorem 4 the covering number of the hypothesis space family Hy oF for meta learning (over tasks) in Theorem 3 is converted into the multiplication of the covering number of the class F of the feature embeddings (over one task) and the n-th power of the covering number of the class Gi of the prediction functions (over one task). This means that we can introduce recent covering number based theoretical results of deep neural network from single task learning into meta learning (see Remark ( In particular, by bounding the covering number in Theorem Q with the Lipschitz constants of the function in each layer of the deep neural network, we can achieve non-parameter-coume based bounds (or say norm-constraint--asee bounds (Neyshabur al. 2017)) for meta learning, which will be detailed in the next section.
4.3 SPECTRALLY- BOCTTRALLYNNORMALIEEE BOUNDS FOR META LEARNING WITH NEURAL NETWORK
Based on the theoretical results in Section 4.2 we now aim to derive non-parameter-coont-booe speotrally-normaliiedd bounds for meta learning with deep neural network. We consider the L-layer depth fully-connected networks with nonlinearities (e.g., activation functions, pooling operators) for each layer, which computes an embedding function f Rd - Rd where do, d are the dimension of input data and embedded feature, respectively. Each layer of the network has a weight matrix A, and ipsciiti nonlinearity og with (0) 0 Then the composition function is given as
7

---

Published as a conference paper at ICLR 2022
ojoA;: : - ,d, e [4]. For any A (A1z)...) (1
A,), any input data z E X, define fa(z) E R.. Let F denote the class of functions computed by the corresponding networks, and D the maximum of {do. di....,dd dr d)..
oz OL(ALOL-I(AL-1 ...
Further, define a sequence of reference matrix (M1 M2) with the same dimensions as (A1, u.. Az), where M; 0 in AlexNet (Krizhevsky al., 2012) and M, I in ResNet (He) et al. 2016) to ensure good generalization performances. Let lo denote the spectral norm, and Tet l.l... denote the (p. q) norr defined by ||Al|p. = ||(l| pp... || p>)1, for matrix A E Rd We next give a spectrally normmlilyy meta-learning bound with deep neural network. For the ease of presentation, we bound (Vy C1 C1+nC2)
with Oly
C2
C2
Theorem Let () be an almost re-rttd environment on the complete separable metric space 7 = XxY. Y. Let H = ={HA}= = (GofA : SA E F,A= (A1,..,,A AL), |A:]la 8t, A M, 2.11
b, i E [L]] be a hypothesis space family where each H. is of the form HA = GofA fA):
g = goW, W R2xd [|2 S 0}, where a is an element-wise function with Lipschitz constant
On Suppose that 36 > for any X C Rdo, || S b. Suppose that the loss function I satisfies
two conditions: (1) when composed with gc.. is an a-Lipschitz function w.r.l. the norm 11-1|,
d fixed y E Y: (2) V fixed v R. fixed y Y, Vg Joo. g' ooW' E G. 33 > 0, such
that (9. 3) - (vV 4)1 I W - W'ull2. Then for any H. E for any 0 < < 1/8, with
probability at least
8 over 2, we have
64 mn
8b ShII-111P1 [av/n In (2D2) c/mn
L
lerx (Ha))H (PL()
In
Σ
30 v n (2dk))
When the loss function ((: is 7-Lipschitz function w.r.t the norm 11.112, we can set a = -0,0, = 78.. This is a very useful corollary for a large number of general applications, such as the multiclass classification and regression problems in the following subsections. We also show in Remark of Appendix that the above bound informative for two-layer neural network.
4.3.1 A SPECTRALLY OPECTRALLY-NNRRMALIEEE NORMALIZED BOUND FOR BINARY CLASSIFICATION
We first consider the binary classification problem under the meta learning framework, where Y (0. 1). We choose the classical logistic regression model due to its simplicity and wide applicabiliy in binary classification scenarios. Formally, let foow w Rd, ||l|] I 0) Fl be the class
of prediction functions, where a is the sigmoid activation function (v) = Ite
[0, 1)). Let
gi f v) (((1.)) y) be the loss function on (I. y) where g (v. y) -y -yln(o(w) (w))) (1 v) In aw v)) is the cross-entropy loss. We then have the following claim.
Claim In the binary classification problem as described above, Vy E EY, g((: y) is a 20-Lipshcitz function w.r.t. 12-norm. Further, fux E TVd y E {0, 1}. then we have Vun, W2 E Rd. [[(w] T v,y) kwy U. y)1 S 2|w; v - -ww vl. Thus, we can set a = 20, 3 = in Theorem 5 to obtain a spectrally- normalized bound for binary classification with logistic regression model in meta learning.
4.3.2 A SPECTRALLY NORMALLZED BOUND FOR MULTICLASS CLASSIFICATION
We further consider the multiclass classification problem under the meta learning framework, where Y [1,..., ()((k 2 3). Let G = (W E R ||W ||2.1 S 0} be the class of prediction functions, and 4 (a)
E F.g E G) be the loss on (I, v). (,(() called the margin loss and p a positive margin parameter. M(gof(z),v)
min (1, (0, -) is
max idy (x) (x) is defined as the margin on (x, y). From Lemma A.3 in (Bartlett et al. 2017) about the Lipschitz property of the margin loss, we have another claim.
Claim 2 In the multiclass classification problem as described above, for any y E Y, the loss func- tion 1(- y) = MM 3) is 2/p- Lipschitz w.r.. the norm 11: Then we can set ? = 2/p and 9, = (a is the identity map in this case) in Theorem and derive spectrally-normaliaaa margin bound for multiclass classification in meta learning.
'In the binary classification, H. = fafA can be considered as the set of the functions from X + IR (not X + Y (0. }}, but the loss functions erq (H)) and erz (HA) are still well-defined. We use this notation just for simplicity and concision. Similar treatment can also he found in the multiclass classification problem.
8

---

Published as a conference paper at ICLR 2022
4.3.3 A SPECTRALLY- NORMALLZED BOUND FOR REGRESSION
For completeness, we finally consider the regression problem under the meta learning framework, where Y = [0, 1J. Let 9 = foow : w E R ||||| | S 0 be the class of prediction functions, where is the sigmoid activation function ((v) = Ite- (E [0, 1]) with the Lipschitz constant 1/4 (note that the derivative a' d'(w) = (1) a(v) S 1/4). Let the loss function be the squared loss function by defining graf v) (a(w" f(x)) (f F,g e G).
Claim In the regression problem as described above, for any y E Y, the loss function K[: y) is 2-Lipschitz w.r. Then we can set = 2 and 0 1/4 (o is the sigmoid function in this case) in Theorem and derive spectrally-normaliced bound regression problem in meta learning.
4.4 WHEN THE ENVIRONMENT IS ALMOST II-RELATED?
In this section, we explore when the given environment (P.Q) is almost II-related, i.c. whether there exists common underlying distribution I' that is almost l1-related with any measure P. sam- pled from the environment. As the discussion below the Definition 3 shows, the most crucial step is to find an (almost) bijective transformation π which satisfies the conditions (1)-(3 in Definition 3 We claim that this bijective transformation is actually equivalent to the almost isomorphism between two probability measure spaces (Chapter 9 in (Bogachev) (007 ). We first give the definition of the almost isomrrphism and the proof of Theorem 6 can be found in the Appendix.
Definition 7 (Almost Isomorphism) Let (Z,,A,1) and B,v) be two measure spaces.
A point isooopphism æ of these spaces is a one-to-one mapping of Zi on to Zo such that pow and Tt (A) B. That is, VAA E (AA) B, and vice versa.
(2) (Z1, A. μ.) and (Z2. B, v)) are called almost isomorphic if there exist sets N1 E Ay, N2 E B, with (NN) (N2)) 0 and point isomorphism of the spaces Zi N1 and 22)N22 that are equipped with the restriction of the measures Ps and v and the complete o-algebra Ap and B..
With claborate treatment, we can reveal the existence of the almost isomorphism between any two complete separable metric spaces. That means, there exists a common distribution P that is almost II-relaedd to any distribution sampled from the same environment. It is formally stated as below.
Theorem Let (P, Q) be an environment on the complete separable metric space Z. Then for any atomeless P., E P(i + j.ú,j E I), the probability measure spaces (Z, B,, P.) and (Z, B,, Pş) are almost isomorphic. In other words, the two measures P. and Pj are almast II-related.
From Theorem 6 we have seen that, any two atomless probability measures P., Pz + j) on the complete separable metric space Z are almost II-related. Therefore, we can choose Pi E as the common distribution that is almost II-related to any probability measure P.(i E Σ) sampled from the set P. Hence, we demonstrate the existence of the common distribution P defined in Definition 5 Further,
drop the condition of the Il-relatedness of all tasks sampled from the environment (P, Q) in Theorems 2 since this task relatedness requirement is fulfilled by the fact that Z is a complete separable metric space. We also need to point out that, the completeness and separability are both very general topological properties that can be satisfied by number of metric spaces such as the real space Rd, the closed subspace in Rdd and the product space of the complete separable metric spaces. For example, in d-dimensional regression problem, the sample space Z = Rd x Ja, b] (a. E R) is also a complete separable metric space.
CONCLUSIONS
This paper provides covering number based generalization bound for meta learning by exploit- ing the task relatedness of the environment. When analyzing the meta learning with deep neural network, we derive spectrally-normalizee bounds for classification and regression problems. Our bounds rely on two basic assumptions: the relatedness between different tasks and the closure prop- erty of the hypothesis space. We demonstrate that, the first task-relatedness assumption can be satisfied if the sample space is a complete separable metric space. We also show that the closure property assumption holds when the hypothesis space contains good solutions as well their equiv- alent variants. Our ongoing research includes analyzing the convolutional neural network as well as establishing sharper generalization bounds for meta learning via algorithmic analysis.
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
Jiechao Guan sincerely thanks Dr. Qi Meng from MSRA for helpful discussions and insightful comments the writing of this paper. We thank anonymous reviewers for spotting mistake in the original proof of this paper. We also thank all reviewers for their constructive suggestions improve the quality of this paper. This work was supported in part by National Natural Sci- ence Foundation of China (61976220 and 61832017), Beijing Outstanding Young Scientist Pro- China Unicom Innovation Ecological Cooperation Plan, and
gram HUUWW2]H01221910002000000 Large-Scale Pre- Pre-Training Program 468 of Beijing Academy of Artificial Intelligence (BAAI).
REFERENCES
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-Bayes theory. In ICMI,, pp. 205-214, 2018
Martin Anthony and Peter L. Bartlett. Neural Network Learning Theoretical Foundations. Cam- bridge University Press, 2002.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. ICML, pp. 254-263, 2018.
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. neeemallyynorrmaizzed margin bounds for neural networks. In NewrIPS, pp. 0240,,249, 2017.
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly- tight VC-dimension and Pseudodimension bounds for piecewise linear neural networks. JMLR, 20:63:1-63::11 2019.
Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12: 149-198, 2000.
Shai Ben-David and Reba Schuller. Exploiting task relatedness for mulitple task learning. In COLT, pp. 567-580, 2003.
Yoshua Bengio, Aaron C. Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE TPAMI, 1798-1888 2013.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenki dimension. JACM, 36(4):929-965, 1989.
V. Bogachev. Measure Theory. Springer-Verlag Berlin Heidelberg, 2007.
Jiaxin Chen, Xiao-Ming Wu. Yanke Li, Qimai LI, Li-Ming Zhan, and Fu-Lai Chung. A closer look at the training strategy for modern meta-learning. NeurlPS, pp. 396-406, 2020.
Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In ICLR, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In ICML, pp. 1126 1135, 2017.
Suriya Gunasekar, Blake F. Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Sre-
bro. Implicit regularization in matrix factorization. In NeurIPS, pp. 6151-6159, 2017.
David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learn- ing applications. Information and Computation, 100(1):78-15) -5000,0 1992.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings deep residual networks. In ECCV, pp. 630-645, 2016.
Mikhail Khodak, Maria-Florina Balcan, and Ameet S. Talwalkar. Adaptive gradient-based meta- learning methods. In NeurlPS, pp. 5915-5926, 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In NewrIPS, pp. 110--1114 2012.
10

---

Published as a conference paper at ICLR 2022
Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-SGD: Learning to learn quickly for few shot learning. arXiv: 2017.
Andreas Maurer. Transfer bounds for linear feature learning. Machine Learning, 75(3):327-350, 2009.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. JMLR, 17:81:1-81:32, 2016.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization deep learning. In NeurlPS, pp. 5947-5956, 2017.
Anastasia Pentina and Shai Ben-David. Multi-task and lifelong learning of kernels. In ALT, pp- 194-208, 2015.
Anastasia Pentina and Christoph H. Lampert. A PAC-Bayesian bound for lifelong learning. In ICML, pp. 991-999, 2014.
David Pollard. Convergence of Stochastic Processes. Springer- Verlag, New York, 1984.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In NewrlPS, pp. pp. 4077-40877 2017.
Flood Sung, Yongxin Yang. Li Zhang, Tao Xiang, Philip H. S. Torr, and Timothy M. Hospedales. Learning compare: Relation network for few-shot learning. In CVPR, pp. 1199-1208, 2018.
Sebastian Thrun and Lorien Pratt (eds.). Learning to Learn. Kluwer Academic Publishers, 1998.
Nilesh Tripuraneni, Michael I. Jordan, and Chi Jin. On the theory of transfer learning: The impor- tance of task diversity. In NeurIPS, pp. 7852-7862, 2020.
Leslie G. Valiant. A theory of the learnable. Communication of ACM, 27(11):1134-114 142, 1984.
Vladimir Vapnik. Inductive principles the search for empirical dependences (methods based on weak convergence of probability measures). In COLT, pp. 3-21, 1989.
John von Neumann. Einige sätze über messbare abbildungen. Annals of Mathematics, 33(3):574- 586, 1932.
Colin Wei and Tengyu Ma. Improved sample complexities for deep neural networks and robust classification via All-Layer margin. In ICLR, 2020.

---

Published as a conference paper at ICLR 2022
APPENDIX
A MOTIVATION OF TASK RELATEDNESS
We simply explain our motivation of exploring 'task relatedness' by comparing the differences be- tween single task learning and meta learning in Table I to fully utilize all training samples.
Table 1: The differences between traditional single task learning and meta learning framework proposed by Baxter (Baxter) 2000), where era(?) er²(H) inf (r E infReæ ptr, (l.). The proposal of our task relatedness notion comes from the motivation that probabilities measures {P.}-= sampled from the environment (P, Q) need to be equivalent, namely, almost Il-related.
Setting
Single-Task Learning
Meta-Leamingg
Goal
choose hypothesis H
choose hypothesis space H. E H
Dealing Objective
i.i.d. sample {
i.i.d. (P.)
probability measures
Generalization Gap
erp(h) (h)
erq(H) er=(H(
Requirement
(zi 1m are similar enough i.e.,
(P.) need be similar enough
identical distributed samples.
i.e., equivalent measures.
B DETAILED PROOFS OF OUR THEORETICAL RESULTS
B. PROOF OF THEORETICAL PROPERTIES OF ALMOST II-RELATED ENVIRONEMENT
Proof of Lemma 7 in the main paper.
From Definition EN C Z, such that P.(N.) = 0. Then for any P-measurable set C ZAN,
P(A) Li-/AAAnzAAN AAAIZIN) + -AnNdP 12.N
d.. "...a:d.///.dPo--R(ttt -1,APooT
where the third equality holds due to the condition (3) in Definition 3 and the sixth equality holds
due to the equivalent integral transformation fog ddP = f fdPog. Similarly, recalling P(h,)
from Definition and noticing (N:) is P-measurable from condition (4) in Definition 3 we
have
P.Choo, ' " + +/JTTOT; 'dP; -fRR=/hhaP hdPP -
P(hj).
J/NN
The above second equality holds due to the fact that SN. NemT a bounded function), and the condition (3) of प, in Definition 3
dPP = 0 (since P.(N.) = 0 and h
Proof of Lemma 2 in the main paper. To prove infnem (h) = inf erp, (l)), it is equivalent to prove inf P(h)) inf (b(b),, then it suffices to show that why E Hi, Ah₃ E Hi we have P.(M)) S P(hi)- Since the symmetricity of P and P. (i.e., Potę;" P., Poo:; P holds almost everywhere), can find another hy such that P(h") < P.())). In fact, let ht hen, from Lemma have (.(M) < P(h))
B.2 PROOF OF THE COVERING NUMBER BOUND FOR META LEARNING IN ALMOST Tl- TI-RELATED ENVIRONMENT
Lemma (Theorem 18 in Baxter 2000 Let C H4 -..--HH, be a permissible class functions
mapping (X y into [0, 1. Let VJmm. be generated by 2 2/(22v independent
12

---

Published as a conference paper at ICLR 2022
trials frims (X x " according to some product probability measure P P1 x Pn. For any V > 0,0 < < for any E H. we have
Pr(z E (X x Y) (mx), sup dr cr su (h), crp 44N(wv (8/ H. cxp( (epp((e
H
Proof of Theorem
in the main paper.
Pr(ze (X r) (m.m) suu d, (er (H), epp cH)() > e)
s {P(ZE (m..)) :sup du fer (h), erp (r)(h) > c
Mr
< <NN(ev Hi ex)((x)(eemmmm/))))))
where the first inequality holds due to the Lemma in (Baxter 2000), and the second inequality
holds due to the Lemma 3 in the supplementary material. Let the r.h.s. of the above inequality be
less than the confidence parameter 8 E (0, 1), then we have c² 2 pmn gives the explicit PAC-style generalization bound on d erp (H)] Theorem 1
In 4N(e2/8, de) which
8
Proof of Theorem 2 in the main paper.
According to Lemma 2 there exists a common distribution P E P such that err(H) = erp (H)
for any P. E P. Then (H) = Jp pr (H))Q((P) = Jp (P))))(((()) = erp(H) 1/n ビØ= erP, (H) = eF)(H), which indicates (erq(H) -rp(HH) O.
Proof of Theorem in the main paper.
By the fact that the loss function has range [0, 1]. and the triangle inequality of metric de
ler (H) -ra((()
S
8
(N(ev/8,HH d)) dz)
I (10)r,((,,rr((((( (71) + d er
In
vmn
6
Letting y (to minimize vv + gives the result.
B.3 PROOF OF COVERING NUMBER BOUNDS FOR META LEARNING WITH REPRESENTATION LEARNING
Proof of Proposition I in the main paper.
Fix an empirical measure Pa on (X x Y)", and let f be a minimum size cover for (F, dpp))))) then we have |F = NNe,,, d()). and vf E F, E f such that d(Pasrr)(..)) s 61. For any E F. let f be the induced probability measure on (V Y)" by defining Pfof (A) = (A)))(A)) VA e o-algebra on (V x Y)". Let Gj be the minimum size cover for (GT) (P.ddRof-).. Hence | ((e2. d s (E2, ,7, 2m). Let {gof : f f and g E } then we have |N] < NV,,,, o 97,, 2m), which satisfies the required cardinality condition.
It remains to show that N is an Eι + cover of H.. Actually Vgl ... @ gnof E HH, choose f F such that (fr.s:((f.f) s en, and choose g @ ... 9 Gj such that d d (01 + ... + In. oi @ ... e gn) I 62. Then the triangle inequality of the distance met- ric d₂ implies that
de(g1 @ ... .....gga... Gg. df @ ......0g.) o
<de(gi 1 ... ... fg. . . gn de .... .....g.of.ff @ ...ff)
<dpp f p. - (g) 0 2 Hn. gi 1 ... 3 g/))
Sel + t
13

---

Published as a conference paper at ICLR 2022
The second 2m 1/2m i=1 yegr (z,) gof(2,)
inequality
holds
due to the definition of d(p.or9)ff)
and the equivalent integral
transformation
gddPa S go Vg E 9i.
2 in the main paper. For any J. E F, we have
Proof of Proposition
2m
(P)
sup [gof(z,) gz.)
2m
gesf
2m
sup
gfof(Zz)) - (
2m
i=1 9
sup 1a (g)o (z
11
2m
93 Edi
S max 13j5n
(f,
which completes the proof of the first inequality. Similarly, for the second one, vP Q" p2m Vg.g I E 9j,
2m
dr, (g. = Σ
(s(s)) - -g' (8(:))
2m
1=1
9 (Vey. 06)) - (1 voyi
2m
2m
1gs (Viy, - (1ish weli
2m
1=1
1 2m
max Snnn
Σ
(, (1ig.81))) (1))
2m
max dp,, (g) isisn
Therefore, N(c, (r,.9r,pp)) dp.) (le,, (i,, 2m)".
I LmaxisisnNNCe E1, ))" and thus WCc, gr, 2m)
B.4 PROOF OF SPECTRALLY-NORMALIE BOUNDS FOR META LEARNING WITH DEEP NEURAL NETWORK
To demonstrate Theorem in in the main paper, need give the following two important lemmas, which gives the won-parameter-count-eee in the single task learning.
spectrally-normaaized bounds for deep neural network
Lemma 4 Bartlett al. 2017) Let positive reals (a, B) and positive integer ls be given. Let matrix V E @Raxxd be given with |V lla S 3. Then
N([VTA A: A:: dx (Hb) =0001
Lemma 5 Bartlett et al. 2017) Let fixed nonlinearities (aI,..., σ1) and reference matrices (Mi..., Mr) be given, where o, is pi-Lipschitz and (0( = 0. Let spectral norm bounds ($1, St), and matrix (2, 1)-mrrm bounds (bI,..,, b1) be given. Let the input data matrix X E R2mxdo be given, where the m rows correspond to data points. Let Hx denote the family of matrices obtained by evaluating X with all choices of network SA Ht [fA(X ))A
14

---

Published as a conference paper at ICLR 2022
(A1, AL), |AAllo I 8,, ||A M, 11,,1 S b,), where each matrix has dimension at most D
along each axis. Then for any > 0,
XI1 In (2D²)
L
8
Proof of Theorem 5 in the main paper. First, we bound In F,, For any P E P, ~~ p2m, for any La SN EF,
2m
(Pa:
1
Σ
sup [()of((z)) - (z:)
2m
siegi
1 2m
sup
un) (f
2m
2m
f((a)))) - (xx(2)) (Lipschitz)
2m
α
ff fxx(X l2.. (Jensen)
22m
Applying Lemma
we then have
v 22m
S InN(
F.11-112)
(I)
In (2D²)
b 33)
a²t2 (2D2)
2
b
3)
2mc²
2
85
Next, bound In (c, Gt, dr:). Actually, for any P 0,5
p2m for any gl, g6
Gr, using
condition (2) of the loss function I and Jensen inequality, we have
2m
dp,
Σ
s (v u1) g/ 9:)l
2m
2m
3
We: W' W' -
I
- V WT
2m
/2m
where V = (U1, U2m) E Rdx2m
Then combining the above results and Lemma
we have
In, Gr dp,)
V2ne B
< InnV
(V
W
11,,1 S 11.11-112)
(2)
820
82000 I1 stt In (2dk).
(2dk)=
<
2m
The last inequality holds due to the Lipschitz property of the activation o and the matrix Ar(1 1, ,.... L.), vi [2m]
||ull2 = (A ... (1) ... -
L
lll S SIPi-
I=1
Recalling Theorem 4 in the main paper and Eqs. I in the supplementary gives the result.
Remark (A situation where our spectrallynormmaized bound for meta-learning is informative)
We further provide situation where the neural network is two-layer network (i.e. composed of
15

---

Published as a conference paper at ICLR 2022
hidden layer with D units and output layer) for k-class classification problem, to provide more information of our spectrally normalized bound from two aspects: (i) Our bound in Theorem is more informative than the traditional VC-dimension bound. Actually, our bound in Theorem for two-layer network can be rewritten as follow:
64 mn
In
Shs1P1 cymm
aay In (2D2 - + 30, (2dk))
Under the same setting, the VC-dimension based meta-learning bound for neural networks (i.e. obtained with techniques from Theorem in Baxter 20000) is of order O(v - / "h Further note that the VC-dimension of the neural networks is RC W W (where W is the total number of the parameters, see [Brrllttt et al. (2099), thus
which of order O D
$1 "IvinDRR) vm
Vnm
the VC-dimension for two-layer neural networks is about R (D² + Dk) In (T)* + DK) and the (D*++R) +Dk)) ), which looser
meta-learning bound is about Ogy (D*+DR) (D*+DK)
than our spectrally-normmalzzed meta-learning bound of O by Vivnn D s (1k)) (ii) Our bound in
/om
V'
Theorem 5 is informative under the implicit regularization framework of SGD. Note that SGD can always find a minimum trace/nuclear norm for neural networks (especially for two-layer networks, see Gunasekar al.) (2017)), therefore the norm parameters 81 and b1 our bound for two-layer neural networks can be small, and hence our spectrally-nowe normallzd meta- weea-llarning bound of order vin D2 $1 /1 (Dk)) can be informative.
O
Vnm
Vm
Proof of the Corollary under Theorem in the main paper.
Fun, 02 E RRd Vy EY,
(v)(v).)) - 9 (V2, v) = ([g(v))) -((g(2)),)) = =ll(oWWn v) - l(aoW 02, v) - W W S 70,00101 -2212:
where the second inequality holds since || ||2,1 a kind of matrix norm of W. Hence we can set = -0.0. Similarly, Vg.gg of E Gr, e E Rd, y E Y, we have (g((v, y) g/ v)l
= =WoooWee,
I(ooW'n v. y)1 S 70, || Ww W'
Then can obtain 3 70, Combining the above results with Theorem gives the result. Proof of Claim in the main paper.
You E Rd, (v.vv) - yn((o(w v)) (1 v) In(1 ow T)). Therefore, Yo1, U2 Rd we have
(1 y) (1(2.))) v)l
+ c 01
=lv(w" w 01) + In
+ ṭ: 02
+ e Tv
</w0 0/2 w T v1l In
+ T Dz
<2ww T 02 w Tul (In(1 + e²x) is Lipschitz)
<2011 vn (Schwarz and ||w|/2 < |||]])-
Similarly, since 1w v) (n( v)) - (1 v) In(1 - oow v)), for any y E {0, 1) we can obtain
+ e
[w v. I(w) v, v) = (uwwTy -w v) + In
+ e S 2/w w/ vl.
Proof of Claim Fin the main paper. For any fixed y [0, 1), for any U1 Uy E Rd, notice that both g(vz) and ((2)) also lie into the interval [0, 1]. then
[[((v)), ((0(12), v)1 ((((v)) - y)² - w)21 S 2)g((1) ) g(v2))-
16

---

Published as a conference paper at ICLR 2022
B.5 PROOF OF WHEN THE ENVIRONMENT ALMOST II- TI-RELATED?
To obtain complete proof of Theorem 6 in the main paper, first give an important lemma that states the existence of the almost isomorphism between a complete separable metric space and the unit interval [0, 1]. We also introduce the formal definitions of metric Boolean algebra and metric Boolean isomorphism (Bogachev 2007).
Theorem Bogachev 2007 Let (2, be complete separable metric space with a Borel prob- ability measure Then (Z, p)) is almost isomorphic to the space ([0, 11, where u is some Borel probability measure. If μ. an atomless measure, then one can take for Lebesgue measure.
Definition 8 (Metric Boolean Algebra) Let (Z, B. be a measure space with a finite nonnegative measure μ.. Let d(A, B) p(AAB), A, B E B. The function d is called the Frechet-Nikodym metric and we can introduce the following equivalence relation on B: A ~ B if d(A, B) O. Then the metric space (B/p, (u, d) is called the metric Booleun algebra, or measure algebra, often denoted by Ew.
Further, the metric space (B/ d) is separable,ie..contain a countable everywhere dense subset, if and only if the corresponding measure μ is separable. The separability of µu is equivalent to the existence of a countable collection of sets B, E B such that VB E B and > 0, there exists an integer n with μ B.. I e. In addition, a metric space (B/u, d) is complete if B is o-algebra and is countably additive (e.g.. is a measure).
Definition 9 (Metric Boolean Isomorphism) Two measure algebras Eu, and Eug generated by mea- sure spaces (Z1. B1. H1) and (Zz, B2, P2) are called isomorphic if there exists a one-to-one mapping I from Ey, onto Epp (called a metric Boolean isomorphism) such that preserves the measure, ie., p2 (A)) (A), AA E Emy-
Theorem (Bogachev 2007) Every separable atomless measure algebra is isomorphic to the mea- sure algebra of some interval (e.g., [0.1]) with Lebesgue measure.
Definition 10 (Lebesgue-Rohlin Space) A measure space (2, j)) is called a Lebesgue-Rohlir space if it is almost isomorphic to some measure space (7', B', ,p() with countable basis with respect to which Z' is complete.
Example The space (I0, 1], B(Jo, 1]), A). where X is Lebesgue measure, has a countable basis with respect to which it is complete.
Theorem vvon Neumann 1932) Let (1, and B2,BB,,12 be Lebesgue-Rohe spaces with probability measures. If the corresponding measure algebra Ep and E,z are isomorphic in the sense of Definition 9 then there exists an almost isomorphism between these spuces. In particular, this is the case if both measures are atomless.
Proof of Theorem 6 in the main paper.
The proof contains main steps: (1) Since Z is the complete separable metric space and the prob- ability measures P., Pj are atomless, then from Theorem 7 (Z, B,, P.) and (Z, B,, Pj) are both al- most isomorphic to the measure space ((0, 1), B( 1)). X) where À is the Lebesgue measure. From
Definition and Example (2, B,, P.) and (2, B, P,)) are Lebesgue-Rohlin spaces. (2) From Ex- A)) (w.r.t. the measure and A(M) 0) has a countable basis {B, | c [[0 11)x The almost isomorphism т; from (J0, 1), B[ A) into (Z, B,, P.) can induce countable basis (B.)) C B, which guarantees the separability of the measure algebras Ep., The separability of the measure algebras Er, can be guaranteed in the same way. Then from Theorem 8 the measure algebras E'p, and Σp,, generated by measure spaces (2, B,, P.) and (2 P2). are both isomorphic to the measure algebra of the interval [0. with Lebesgue measure. Therefore, the two measure algebra Ep, and Ep, are isomorphic (since isomorphism is equivalence relation). (3) Combining (1) and (2), and recalling Theorem | the two measure spaces (Z, B,, P.) and (Z, P3) are almost isomorphic. So P, and Pa are almost II-relatdd in the sense of Definition 3
ample [ the complete measure space (j0, M,
17

---

Published as a conference paper at ICLR 2022
C MORE DETAILED COMPARISONS WITH RELATED WORKS
C.I DETAILED COMPARISON WITH GENERALIZATION BOUNDS OF (BAXTER 2000)
This paper can be considered as the extension of the meta learning theoretical work in (Baxter, this section, we detail our
2000), by further exploring the task relatedness for the environment. improvements over this pioneering work. First, we introduce a notation called H*. For any hypothesis space H E H. define H. P + [o, 1] by H (P) = infΛeH (hf))) and for any hypothesis space family IHI, define THI* = { H E H.). Although Baxter does not give the explicit PAC-style learning bound in his main paper, its bound on |er (H) erq (H)) can be expressed as:
64 mn
8C(e/8, In
64 n
In 8C(c/8,H))
8
8
supo Nee, H", .d)) (see its Theorem 4). Our improvements can be summarized the following three aspects:
where C(e, HIp) ((e, HP,, , dp,,
(1) We exploit the proposed task relatedness to reduce the complexity C(e, H in Eq.
zero in 3 In Theorem [6, we further show the rationality of our task relatedness assumption when the sample space Z is a complete separable metric space. Given that (Baxter 2000) also assumes 2 to be a separable metric space to obtain theoretical results, our derived meta learning bound in Theorem []] albeit depending on slightly stronger assumption, is a non-trivial enhancement. Nev- ertheless, we admit that our results also rely on the closure property of the function class H4, (2) Our covering number results (e.g., Theorem 4 are based on the metric defined w.r.t. the empir- ical measure, instead of the abstract measure in Baxter's 's work (e.g., Theorem 6 in (Baxter ) Therefore it is more suitable to combine our results with the recent theoretical results of covering number bounds for deep neural networks in single task learning.
Theorems
(3) When bounding the covering number (or say capacity) of the neural network C(e2, F) (i.e., The- orem 8 in (Baxter 2000)), Baxter uses traditional Pseudo-dimense
indicator which is developed by (Haussler 1992). resulting in a parameter-coum coae---ottttttcdccdeeeee bounds for meta learning with neural net- work. However, this is not suitable for the analysis of modern overparameterized deep networks. In this paper, we introduce a new complexity indicator, spectrally normalized bound for deep neural network (Bartlett et al.] 2017), into the meta learning framework. The obtained bounds for meta learning with deep network for classification and regression problems in Claims 1 are all indepen- dent of the size of total parameters, outperforming the results in Theorem 8 of (Baxter 2000).
(The three main technical difficulties when applying spectralty-normalized margin bounds for meta-learning with deep neural networks)
Remark 2
Now, we give more explanations about the three main technical difficulties when applying spectrally- normalized margin bounds (Bartlett et al.) (017) for meta- veta-learning with deep neural networks.
(i) We need to remove the second covering number complexity (i.e. the covering number complexity of H²)) in the meta-learning bound in Eq. (3) in Section C. (i.e. the original bound in Theorem 4 of (Baxter, 2000)). Since such covering number complexity is defined (and can only be defined) based on the distance with respect to the abstract measure (instead of the empirical measure, see Defini- tions 3-4 in (Baxter 20000), we cannot use any modern theoretical results in deep learning (c.g.. the spectral norm of the neural networks in (Bartlett et al. 2017), the compression bound in (Arora et al., 2018) and the ALL-layer margin in (Wei & Ma 2020) but the traditional VC-dimension to bound such covering number complexity, hence leading to the vacuous parameter-count-basee bounds for deep neural networks. The aforementioned challenge motivated us to propose the II-relatedness notation to measure the similarity between different tasks and finally removed the second covering number complexity in Eq. (3) to obtain our main generalization bound in Theorem 3 that can fully utilize the whole n * m training samples.
(ii) For the first covering number complexity in Eq. (3) (which is still defined based on the dis- tance w.r.t. the abstract measure in Baxter's ' original paper), we still need to transform it into the complexity defined on the distance w.r.t. the empirical measure with our proposed techniques in Propositions (also see our Definition G). hence we can extend our generalization bound in The- orem 3 to the representation setting and make our meta-learning bound with representation learning (i.e. Theorem 4 much casier to be combined with modern theoretical results (Bartlett et al.) 2017 Arora et al. 2018 Wei & Ma 2020) for deep neural network in single-task learning.
?
(iii) The last difficulty is connect the covering number complexity in meta-learning setting (e.g.
18

---

Published as a conference paper at ICLR 2022
our Definition w.r.t. the empirical measure) with the speetrallynoormalin based cover- ing number complexity from Bartlett et al. (2017) (i.e. Lemmas 4 in our Appendix [B44) Such difficulty is overcome by using the Lipschitness property of neural networks and the theoretical properties covering number (see the proof of Theorem in Appendix B.4).
C.2 DETAILED COMPARISON WITH TASK RELATEDNESS NOTION OF (BEN-DAVID & SCHULLER 2003)
In this section, we detail more distinctions between our proposed almost I-relatednnss notation and the task relatedness notion defined in "Ben-David Schuller, 2003). We first recall this previous concept in (Ben- (Ben-David & Schuller 2003 Definition 2.1).
Definition 11 (Ben-David & Schuller 2003) Let F. be set of transformations f x X and let PA, P2 be probability distributions over X {0, 13. We say that P1, P2 are F-related distributions if there exists some f E F such that for any T C X x (0.1), T is P1 P1-measurable iff
f[T] {1)()). ())(z) b) E T) is Pz-measurable and (T) = Pa(fTT).
Remark (The main differences between our task relatedness notation and that of (Ben-David & Schuller 2003)
Note that in Definition 11 the condition (T) = P2(f(T) means that Pi(T) = o (f x [] for all T c X x {0, Therefore P1 = P2 (f x 1) and hence f x 1 is a (bijective) measure- preserving transformation on the product space x {0, 1}. Recall the definition of our proposed task relatedness concept in Definition in the main paper. It's not diffieult to see that there are two main differences between these two task-relatedness notions: (i) The bijective transformation f in Definition II of David's work defined between the input space X and the input space X. While in our work, the bijective transformation π in Definition 3 of the main paper is defined between the sample space Z(= X x Y) and the sample space Z. Note that the bijective transformation f in Definition [1 can be viewed as the bijective transformation f x I on the product space X x Y. where the identity map on the output space Y. Therefore the transformation given by (Ben-David & Schuller (003) can be considered as a special case of our proposed task-relatedness concept. (ii) Furthermore, the bijective transformation given in Definition [ is a function map imposed on the whole input space X, whereas our proposed bijective transformation is imposed on the almost whole sample space excluding a measure-zero set. In other words, our proposed π is a bijective map between N and Z NV, where N, P-measure zero and P1 P1-measure zero sets, respectively. Such design will allow more flexibility of the choice of the bijective map m, and can help theoretically guarantee the existence of the almost bijective function on the whole sample space 7 (see more explanations in Section B.5). In contrast, (Ben-David & Schuller] 2003) does not provide a rigorous demonstration of the existence of its defined bijective transformation f. Actually, it is not easy to find such bijective transformation f on the input space X, which meanwhile satisfies the condition that the bijective transformation f is a measure- pressrrep bijective on the product space X x Y. In this sense, our work can be considered as the extension version of that in (Ben-David & Schuller 2003).
As for our proposed task task-relatedness concept, the explicit form of the bijective transformation æ in Theorem main paper can be found in (Bogachev 2007 Theorem 6.5.7). In that result, Bogachev takes π as the composition of functions Σ 2x=1 JE, and (_a= LB.,) 11, where E,, belongs to the o-- algebra B, over the sample space Z associated with the measure μt, B,, belongs the o-algebra B, over the sample space Z associated with the measure v, is the indicator function from the a olalgebra over Z to the interval [o, 1]. A simpler (but not rigorous) example just for intuitive comprehension can be found in the regression problem, where the sample space is Z = Rd+1 = X x Y R2d x IR, the focused measure is Lebesgue measure and the bijective function æ . (2) translation over ligh-dimensional Euclidean space.
ā Z is
19


Reviews:
[{"review_id": "pF1dutuvP5w", "reviewer": "Reviewer_VEYq", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Significance: The paper takes a meaningful and important step towards developing meta-learning theory. The paper addresses one of the key issues in Baxter (2000) of not being able to fully utilize m*n training samples. This is done by imposing the task-relatedness assumption on the task environment. The paper later provides upper bound on the covering number, particularly in the representation learning with neural network setting.\n\nNovelty: The paper follows Baxter’s framework, and the notion of task-relatedness is also previously studied in Ben-David & Schuller (2003), albeit with some differences (highlighted by the authors in the appendix). This distinguishes itself from recent meta-learning theory work, e.g., Du et al. (2020), and Tripuraneni et al. (2020), that study meta-learning for a fixed target task using the notion of task diversity/similarity. \n\nPresentation: The paper writing and presentation is great. The related work is discussed in good detail. The connection between the proposed theory and existing literature are highlighted and discussed. \n\nWeakness: From what I understand, the proof of the key results uses techniques and results from existing works. The PAC-style generalization bounds (Theorem 1, 2, 3) use results from Baxter (2000). The covering number bounds with deep neural networks (Theorem 5) use results from Bartlett (2017). It would be nice if the authors can highlight some challenges/difficulties in adapting existing results.\n", "summary_of_the_paper": "The paper presents generalization bounds for meta-learning (Corollary 1) that obtain O(1/sqrt{m*n} * log{covering number}) convergence rate. Unlike previous work, the proposed bound can utilize all m*n training samples (n tasks, m samples per task). In a special branch of meta learning that involves representation learning with neural networks, i.e., the algorithm learns a common embedding that is shared across tasks, the paper establishes spectrally-normalized bounds for both classification and regression problems.\n\nThe paper relies on two critical assumptions: relatedness between tasks and closure property of the hypothesis space. The paper shows that the task-relatedness assumption is satisfied if the sample space is a complete and separable metric space. The paper also briefly discusses the conditions for which the closure property assumption holds.\n", "summary_of_the_review": "The paper makes an important and meaningful contribution to the theory of meta-learning. The paper is well-written, and the ideas presented are sufficiently novel. I think the paper would make for a good submission in ICLR 2022.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ljof7F2l60", "reviewer": "Reviewer_bHHr", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths.\nAs far as I know, the bounds are novel, require some technical skills, and give novel interesting insights for meta-learning.\nThe bounds cover different settings (regression, binary/multi-task).\nThe spectrally normalized bounds are interesting and give more practical insight on the performances of some models.\n\nWeaknesses\nThe practical use of the bounds is not really discussed, how far can we derived new algorithms from these bounds.\nThe elements that can be easily estimated and those that may not could  be better discussed.\nThe information provided by the bounds could be better discussed as well, in particular it not clear if they are informative, maybe giving some situations where the bounds are not loose could be interesting.\n\nAbout the existence of the $\\Pi$-relatedness notion: the authors provide some mathematical frameworks for justifying the existence the $\\Pi$-relatedness notion, this is interesting but remains abstract in a sense. In practice, one can wonder if the restriction on the one-to-one mapping is realistic, but no algorithm/method is given for estimating it. I am wondering if optimal transport, using Kantorovich-based relaxations, can provide a setting where some transformations always exist (up to a barycenter mapping), then maybe notions of Wasserstein distances should be considered here.\n\nA paper that can be related:\nWang H. et al. 2021. Bridging Multi-Task Learning and Meta-Learning: Towards Efficient Training and Effective Adaptation. In ICML 2021 \n\n--\nAfter rebuttal\n--\nI'm ok with the answers provided by the authors, I keep my score.\nAbout OT: my point was to use a kind of \"one-to-many\" mapping provided by the Kantorovich relaxation, but I understand that this not easy.", "summary_of_the_paper": "The paper presents novel generalization bounds for meta-learning based on a notion of task-relatedness that allows one to compare two tasks by notably allowing a mapping only in subregions where the similarity can be measured in a sense. The theoretical results a covering number bound, a covering number meta-learning bound with representation learning, and spectrally-normalized bounds for meta-learning with neural networks adapted to binary, multi class and regression. The contribution is theoretical.", "summary_of_the_review": "The paper presents novel and interesting generalization bounds for meta-learning, they offer new insightful results, in particular with spectrally-normalized bounds that are adapted to learn with neural networks in different settings (binary, multi-class, regression).\nThe practical implication of these results is not really discussed and the perspectives offered by these results for designing new algorithms are not sufficiently developed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ebvkhyTFf16", "reviewer": "Reviewer_fpV1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 1, "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": "With the big caveat that I am not knowledgeable on recent theoretical work for meta-learning to provide a very educated critique of this paper, I felt that proposed $\\Pi$-relatedness notion and corresponding PAC generalization bound involving m*n samples is novel enough to make this paper interesting to the ICLR community. I have not checked the proofs in the Appendix.", "summary_of_the_paper": "The paper:\n1) proposes a new notion of task-relatedness for meta-learning termed \"almost $\\Pi$-relatedness\" that assumes isomorphisms between two tasks in the environment. A PAC-style generalization bound of $\\mathcal{O}(\\sqrt{\\frac{C}{mn}} +  \\sqrt{\\frac{\\ln(1/\\delta)}{mn}})$ is shown, improving upon Baxter et. al's.\n2) For meta learning that involves representation learning, they bound $C$ with two covering numbers that are both defined over a single task, making their results suitable to be combined with recent works of deep neural network in the single task learning.\n3) They demonstrate that any two tasks in the environment are almost $\\Pi$-related if the focused sampled space is a complete separable metric space.", "summary_of_the_review": "Unfortunately, I am not knowledgeable on recent theoretical work for meta-learning to provide a very educated critique of this paper. The proposed $\\Pi$-relatedness notion seems like a novel contribution and the PAC generalization bound involving mn samples seems stronger than existing work, so for that reason I'd lean to accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RaIrML4zehU", "reviewer": "Reviewer_7ER7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "The paper is well-written and comprehensive. Although the paper employed many notations, they are intuitive and easy to follow. Overall I think this is a good paper.\n\nHere are a few specific questions:\n1. Can two multi-class classification tasks with different numbers of classes be almost PI-related? Can two tasks with different number of features be almost PI-related? It is unclear from the paper.\n2. It is unclear to me how we should separate the embedding function f with the prediction function g. Presumably both the embedding and prediction layers are multi-layer networks, and there are various ways to separate the whole network into an f function and a g function. Could the authors elaborate?", "summary_of_the_paper": "In this paper, the authors proposed two key concepts: almost PI-Related tasks and almost PI-related environment. Intuitively, if two tasks are PI-related, then if a function space H contains a good solution to task A, it should also contain a good solution to task B.\n\nWith these two concepts, the authors went forward and proved that in an almost PI-related environment, the generalization bound has a convergence rate of O(1/\\sqrt(mn)). In other words, when tasks are similar, then meta-learning algorithms should be able to utilize all data points across all tasks.", "summary_of_the_review": "This is a well-written paper with vast implications in the meta-learning society. The almost Pi related concepts are useful and easy to understand.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides generalization bounds for meta-learning based on a notion of task-relatedness. The result is natural and interesting--intuitively, when tasks are similar, then meta-learning algorithms should be able to utilize all data points across all tasks. The theoretical contribution is novel, and the results also provide more practical insight into the performances of some models.
Decision: Accept (Spotlight)