TASK RELATEDNESS-BASED GENERALIZATION BOUNDS FOR META LEARNING
Year: 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 O( 1 √ 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.

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

heading: 1 INTRODUCTION
text: By leveraging knowledge distilled from the training tasks1, meta learning (Thrun & Pratt, 1998; Baxter, 2000) 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., 2013; He et al., 2016), where one first learns a shared feature extractor (e.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 a few gradient steps (Finn et al., 2017; Li et al., 2017) or with a feedforward process (Snell et 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 assumes 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 hypothesis spaceH a hypothesis h to achieve the minimal expected loss on the task, meta learning expects to choose from the hypothesis space family H a hypothesis spaceH(∈ H) that contains a good solution to any task sampled from the environment. Under the PAC learning framework (Valiant, 1984;
Vapnik, 1989), (Baxter, 2000) derives a uniform bound of O( √
C1 mn + √ C2 n ) on the expected loss
of a hypothesis space H over the new task in the environment, according to the empirical loss of H ∗Corresponding author. 1In this work, a task represents a data distribution, or say a probability measure on the sample space.
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 O( √
C m ) of any h ∈ 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) ofH, Baxter’s meta learning generalization bound of any H ∈ H cannot fully utilize all mn training samples (e.g., with a bound of O( 1√
nm ), without extra terms of O( 1√ n ) or O( 1√ m )). 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 different 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 distributions actually corresponds to the measure-preserving isomorphism of their induced measure spaces2 (see Definition 7). Therefore in this paper, we define a new notion of task relatedness called almost Π-relatedness in Definition 3 according to the existence of a measure-preserving bijective transformation 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 proposed task relatedness. We further employ this task relatedness notation to analyze the representation learning with deep neural networks, and establish non-parameter-count-based spectrally-normalized bounds for both classification and regression problems under the meta learning framework. Finally, we demonstrate the rationality of our proposed task-relatedness notion from a theoretical standpoint.
Our main contributions are summarized as follows:
(1) We propose a new notion of task relatedness, called almost Π-relatedness, by exploring the existence of a bijective transformation between two tasks in the environment. A novel PAC-style generalization error bound of O( √
C mn ) 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 Contribution (1) with two covering numbers that are both defined over a 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-normalized bounds of O( √
C1+nC2 nm ) for classification and re-
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 Π-related if the sample space is a complete separable metric space, validating the applicability of our proposed task-relatedness measure.

heading: 2 RELATED WORK
text: 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 different 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 Bayes algorithm in PAC-Bayes theory (Pentina & Lampert, 2014; Amit & Meir, 2018). Among them, (Chen et al., 2020) derive a bound ofO( 1√
n ) from the algorithm
stability perspective, and (Pentina & Lampert, 2014) derives a bound ofO( 1√ n + 1√ m )(we 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
2A measure space is a triple (Z,A, P), where Z is the set, A is the σ-algebra on Z, P is a measure on A.
(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 proposed task environment setting, by defining task similarity or task diversity notion, obtaining similar excess risk bounds ofO( 1√
mn + 1√ m ) in the case
of high-dimensional transfer learning. Our work follows Baxter’s proposed i.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.1.
Task Relatedness. Another related work (Ben-David & Schuller, 2003) also proposes a taskrelatedness 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 a 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 is a complete separable metric space, making our results more applicable. The differences between our proposed task-relatedness notion and that in (Ben-David & Schuller, 2003) can be found in Appendix C.2. Besides, (Khodak et al., 2019) and (Du et al., 2021) also consider taskrelatedness notions such as parameter-closeness or sharing a low-rank subspace for meta learning. To distinguish the notions proposed in this paper with others is truly one of our future directions.

heading: 3 PRELIMINARY
text: In this paper, we use uppercase letters (e.g., Z) to represent different spaces. The boldface z represents a matrix, with zi as its i-th row and z;j its j-th column. ~z denotes a vector. All detailed proofs of our theoretical results are deferred to the Appendix B for reader’s benefits.

heading: 3.1 META LEARNING
text: The formulation of meta learning problem can be summarized as follows. We are given a sample space Z = 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 l : Y ×Y → R, and we assume that l has the range [0, 1], or equivalently, with rescaling technique, we assume that l is bounded. An environment (P, Q) is a two-tuple, whereP is the set of all probability measures\distributions\tasks on X × Y and Q is a probability measure on P . A hypothesis space family is formulated as H = {H}, where each H ∈ H is a set of hypotheses\functions h : X → Y . In single task learning, the learner needs to choose an optimal hypothesis h∗ ∈ H to minimize the expected loss of h over a probability measure P (∈ P) on the product space X × Y : erP (h) = ∫ X×Y l(h(x), y)dP (x, y). Similarly, the goal of meta learning is to find a hypothesis space H∗ ∈ 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, Eq.(6)): erQ(H) = ∫ P infh∈H erP (h)dQ(P ). In practice, it is hard to minimize erQ(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 n times from P according to Q to generate (i.i.d.) probability measures P1, ..., Pn. (2) Sample m times from X × Y according to Pj to generate {(x1j , y1j), ..., (xmj , ymj)} (1 ≤ j ≤ n). (3) Denote zij = (xij , yij) ∈ Z, and an (m,n)-sample will be generated, denoted by z and written as a matrix z = (zij)m×n. We then choose to minimize the empirical loss êrz(H) over the training data z for meta learning, which is defined as êrz(H) = 1n ∑n j=1 infh∈H êrz;j (h), where z;j is the j-th column of matrix z. Let P = (P1, ..., Pn). We also consider the following loss êrP(H) as the empirical estimate of the expected loss erQ(H): êrP(H) = 1n ∑n j=1 infh∈H erPj (h).
Definition 1 (Baxter, 2000) For any hypothesis h : X → Y , define hl as the composition of loss function and hypothesis: hl : X × Y → [0, 1] by hl(x, y) = l(h(x), y). For any hypothesis space H ∈ H, define Hl = {hl : h ∈ H} as the function space on Z. For any sequence of n hypothesises (h1, ..., hn), define (h1, ..., hn)l : (X × Y )n → [0, 1] by (h1, ..., hn)l(x1, y1, ..., xn, yn) = 1/n ∑n i=1 l(hi(xi), yi). We will use hl to denote (h1, ..., hn)l.
∀H ∈ H, define Hnl = {(h1, ..., hn)l : h1, ..., hn ∈ H} and Hnl = ⋃ H∈HHnl . Define
P (hl) = ∫ X×Y hl(x, y)dP (x, y) and P (Hl) = infhl∈Hl P (hl) where P is a probability measure on Z, and we have P (hl) = erP (h) and erP (H) = P (Hl).
Definition 2 Let (M,d) be a pseudo-metric3 space. ∀ > 0, a subset T̂ is called an -cover of T ⊆ M if ∀t ∈ T , ∃t′ ∈ T̂ such that d(t, t′) ≤ . Let P = P1 × · · · × Pn be the product measure on Zn. For any (Hnl 3)hl,h′l : Zn → [0, 1], define the pseudo-metric dP(hl,h′l) =∫ Zn |hl(~z) − h′l(~z)|dP(~z). Then for any > 0, the covering number N ( ,Hnl ,dP) is defined as
min{|T | ∣∣T is an -cover of Hnl under the dP pseudo-metric}, where |T | is the cardinality of T .
We hope to use the empirical loss êrz(H) or êrP(H) to approximate the expected loss erQ(H). Instead of the traditional absolute value function d(x, y) = |x−y|, we consider the following metric function (ν > 0, x, y ≥ 0) dν [x, y] = |x−y|x+y+v to measure the distance between x and y, which is first used by (Haussler, 1992). In Section 4, we will bound the deviation dν[êrz(H), erQ(H)] by bounding dν[êrz(H), êrP(H)] and dν[êrP(H),erQ(H)], respectively.

heading: 3.2 ALMOST Π-RELATED TASKS
text: In this section, we first propose a new concept of task relatedness, which is called almost Πrelatedness. This notion can be considered as the extension of the ‘Π-relatedness’ notion proposed by (Ben-David & Schuller, 2003). The distinctions between our proposed task relatedness notion and that of Ben-David & Schuller (2003) can be found in Section C.2 of Appendix C.
Definition 3 (Almost Π-Related Tasks) Let Π be a set of transformations π : Z → Z and let P, P1 be probability measures on Z = X × Y . We say that P, P1 are almost Π-related probability measures\tasks, if the following conditions are satisfied: (1) ∃N,N1 ⊆ Z such that P (N) = P1(N1) = 0, and (2) ∃π ∈ Π, π is a one-to-one mapping from (Z\N,P ) onto (Z\N1, P1). ∀A ⊆ Z\N ,A is P - measurable if and only if π(A) = {π(x, y)
∣∣(x, y) ∈ A} ⊆ (Z\N1) is P1-measurable, and (3) ∫ Z\N 1AdP = ∫ Z\N1 1π(A)dP1, where 1A is the indicator function on the set A, and (4) the image π(N) is a P1-measurable set, and the inverse image π−1(N1) is a P -measurable set.
Note that condition (4) is a weak requirement only to ensure the measurability as well as the integrability of the mapping π (or π−1) on the measure zero set N (or N1). Actually, to validate whether two tasks (say P and P1 ) are almost Π-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 π(N) as a P1-measurable set (e.g. a P1-measure zero set) and extend π−1 to N1 in a similar way, such that the extended transformation satisfies the condition (4). The existence of such transformation between two tasks can be theoretically 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 a closure property assumption of the spaceHl ∈ Hl when the transformation set Π is imposed on Hl. Similar to (Ben-David & Schuller, 2003) which assumes the closure property of any hypothesis space under the transformation Π, we also assume that the closure condition is satisfied by anyHl ∈ Hl for deriving better generalization bound.
Definition 4 Let Π be the set of transformations on the complete separable metric space Z = X × Y . We say that the function space Hl is closed under the transformations of Π, if for any hl ∈ Hl, any π ∈ Π, we have the composition function hl◦π ∈ Hl.
We need to give more explanations to the rationality of the closure property of the function spaceHl, as the closure property is a very important assumption to derive our generalization bounds. Actually, the almost Π-relatedness defined in Definition 3 can induce an equivalence relationship between two tasks, according to the existence of one bijective function π ∈ Π. The function π can also induce an equivalence relationship between two functions in the spaceHl. That means, if a function spaceHl contains a good solution to one task P , then Hl should also contain a good solution to the almost Π-related task P1 of P . Since the two tasks P and P1 are equivalent to some extent, the function space Hl should simultaneously contain the good solutions to these two similar tasks. With such closure property assumption, the complexity of the function space Hl is related to the degree of relatedness between different tasks from the environment. If the tasks in the environment are all similar (e.g., almost Π-related), then it is sufficient forHl to contain one good function as well as its
3A pseudo-metric is a metric without the condition that d(x, y) = 0⇒ x = y.
Π-related variants to generalize well to all tasks. Such closure property assumption of the function space is also considered in Ben-David & Schuller (2003). They have demonstrated that as long as the function space is rich enough to contain some function as 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 spaceHl holds to derive novel theoretical insights for meta-learning. We introduce another concept induced from the π-related tasks, called almost Π-related environment, and its theoretical properties, which will be used to derive our theoretical analysis in Section 4.
Definition 5 (Almost Π-related Environment) In meta learning set up, an environment (P, Q) on X × Y is called an almost Π-related environment, if there exists a common probability measure P on X × Y , such that for any measures Pi ∈ P(i ∈ I, I is the index set), P and Pi are almost Π-related in the sense of Definition 3.
Lemma 1 Let (P, Q) be an almost Π-related environment on X × Y , Hl a function space on 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 A ⊆ Z\N , for any Pi ∈ P(i ∈ I), hl ∈ Hl, we have P (A) = Pi(πi(A)), Pi(hl◦π−1i ) = P (hl), where πi is the corresponding transformation between Π-related tasks P and Pi (as defined in Definition 3).
Lemma 2 Let (P, Q) be an almost Π-related environment onX×Y , P be the common distribution that is almost Π-related to any distribution from P . If a function space Hl (on X × Y ) is closed under the transformations of Π, then for any probability measure Pi ∈ P , erP (H) = erPi(H).
We provide two insights into the theoretical result in Lemma 2 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 on 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 to be large enough to contain good solutions that are invariant to the transformation between different tasks. Hence, insight (1) motivates us to define the Π-relatedness notion to 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 in Appendix A.

heading: 4 THEORETICAL RESULTS
text: We first give a novel generalization bound for meta learning in the almost Π-related environment in Section 4.1. This is particularly achieved by employing the theoretical properties of the almost Π-related environment in Lemma 2. As shown in Theorem 6 in Section 4.4, assuming the environment to be almost Π-related is reasonable when the sample space Z possesses the completeness and separability (which are general topological properties satisfied by many metric spaces). Section 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 spectrallynormalized bound that is independent on the number of the total parameters in neural network in Theorem 5. Moreover, we apply this theoretical result to analyze several practical scenarios like binary\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 C, to show the technical contributions of this work and outgoing research directions for meta-learning.

heading: 4.1 A COVERING NUMBER BOUND FOR META LEARNING IN ALMOST Π-RELATED ENVIRONMENT
text: To bound |êrz(H) − erQ(H)|, we choose to bound the deviation dν[êrz(H), êrP(H)] and dν[êrP(H),erQ(H)], respectively. We first give an explicit PAC-style generalization bound on dν[êrz(H), êrP(H)], which can be considered as an inference of Theorem 18 in (Baxter, 2000).
Theorem 1 Let Hnl ⊆ Hl⊕ · · ·⊕Hl be the permissible4 class of functions mapping (X ×Y )n into [0,1], where Hl = {hl : h ∈ H : H ∈ H}, ⊕ means direct product. Let z be generated by m ≥ 2/(ν 2) independent trials from (X × Y )n according to the product measure P = P1 × · · · × Pn. For any ν > 0, 0 < < 1, for anyH ∈ H, with probability at least 1− δ over z, we have
dν [êrz(H), êrP(H)] ≤ √ 8
νmn ln 4N ( ν/8,Hnl , dz̄) δ ,
where z̄ ∈ Z(2m×n), the top half of z̄ is actually z itself and the bottom half of z̄ is the copy of z. ∀hl,h′l ∈ Hnl , dz̄(hl,h′l) = 1/2m ∑2m i=1 |hl(z̄i)− h′l(z̄i)|.
On the other hand, we can actually bound the deviation dν [êrP(H),erQ(H)] as follow, by using the theoretical properties of the almost Π-related environment in Lemma 2.
Theorem 2 Let (P, Q) be an almost Π-related environment on the complete separable metric space Z = X × Y . Let P ∈ Pn be generated by n independent trials from P according to some product probability measure Qn. Then for any ν > 0, anyH ∈ H, we have dν [êrP(H), erQ(H)] = 0.
Combining Theorem 1 and the Theorem 2, we can obtain a novel generalization bound of convergence rateO( 1√
nm ) on |êrz(H)−erQ(H)| that fully utilizes allmn training data under the proposed
meta learning framework in (Baxter, 2000), uniformly over the set of all hypothesis spaceH.
Theorem 3 Let (P, Q) be an almost Π-related environment on the complete separable metric space Z = 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 1− δ over z, we have
|êrz(H)− erQ(H)| ≤ √ 64
mn ln 4N ( /4,Hnl , dz̄) δ .
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 1 In the setting of Theorem 3, let Pn+1 be the new task sampled from the environment. Then for anyH ∈ H, ∈ (0, 1), with probability at least 1− δ over z, we have
erPn+1(H) ≤ êrz(H) + √ 64
mn ln 4N ( /4,Hnl , dz̄) δ .
There are two important points to note about Corollary 1: (1) If the hypothesis space H contains only one hypothesis and all probability measures in the environment are the same, then the we can choose the bijective transformation π between different distributions as the identity transformation, and the result in Corollary 1 degrades to the traditional covering number based generalization bound in single task learning (see Chapter 10 in (Anthony & Bartlett, 2002)), which utilizes all mn i.i.d. training data. In this sense, meta learning theory can be considered as the extension of the conventional single task learning theory. (2) When bounding the generalization error of a hypothesis space H under Baxter’s proposed meta learning framework, even though different tasks may have different distributions, we can still properly estimate the expected loss on the new task according to the empirical loss on the training tasks, and fully leverage all mn (not necessarily i.i.d.) training data with the use of assumed task relatedness 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).

heading: 4.2 COVERING NUMBER META LEARNING BOUNDS WITH REPRESENTATION LEARNING
text: In single-task learning setup, representation learning aims to 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
4Permissibility (Pollard, 1984) is a weak measure-theoretic condition satisfied by almost all ”real-world” hypothesis space families. Without loss of generality, we assume that all hypothesis space families discussed through out this paper are permissible .
function g ∈ G then projects the feature space V into the output space Y . Hence, the hypothesis space can be written as H = G◦f , (f ∈ F). Further, let Hl = {Hl}, each Hl = Gl◦f , f ∈ F , where Gl = {gl}, gl = l◦g is the composition function of the prediction function g and the loss function l. We will omit the subscript l of gl ∈ Gl for simplicity where the context is clear. In meta learning setup, representation learning chooses to learn a 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 Hnl = {g1◦f ⊕ · · · ⊕ gn◦f : g1, ..., gn ∈ Gl, f ∈ F} = {g1 ⊕ · · · ⊕ gn◦f̄ : g1 ⊕ · · · ⊕ gn ∈ Gnl , f̄ ∈ F} = Gnl ◦F , by defining F 3 f̄ : (X × Y )n → (V × Y )n with f̄(x1, y1, ..., xn, yn) = (f(x1), y1, · · · , f(xn), yn). We then define two pseudo-metrics over feature embedding space F and prediction function space Gnl respectively.
Definition 6 ∀z̄ = (zij)2m×n ∈ Z(2m×n), define the empirical measure Pz̄ on Zn which puts point mass 1/2m on each row z̄i, i = 1, ..., 2m. ∀s = ( (f(xij), yij) ) 2m×n = ( (vij , yij) ) 2m×n, where f ∈ F , define an empirical measure Ps which puts mass 1/2m on each row si, i = 1, ..., 2m. ∀f̄, f̄ ′ ∈ F , define the pseudo-metric d[Pz̄,Gnl ](f̄, f̄ ′) = 1/2m ∑2m i=1 supg∈Gnl |g◦f̄(z̄i)− g◦f̄
′(z̄i)|, and ∀g, g′ ∈ Gnl , define the pseudo-metric dPs(g, g′) = 1/2m ∑2m i=1 |g(si)− g′(si)|.
Then the following two propositions bound the covering number of the hypothesis space family Hnl with two covering numbers that are both defined over the single task.
Proposition 1 Let (P, Q) be an environment on V × Y . Denote N ( ,Gnl , 2m) = supP∼Q̄n sups∼P 2m N ( ,Gnl , dPs). Then for any = 1 + 2, any z̄ ∈ Z2m×n, we have N ( 1 + 2,Hnl , dz̄) ≤ N ( 1,F , d[Pz̄,Gnl ])N ( 2,G n l , 2m).
Proposition 2 Let z̄;j be the j-th column of the data matrix z̄. Let N ( ,Gl, 2m) = supP∼Q̄ sup~s∼P 2m N ( ,Gl, dP~s), where dP~s(g, g′) = 1/2m ∑2m i=1 |g(si) − g′(si)|, ∀g, g′ ∈ Gl, ~s = (s1, ..., s2m). Then for any > 0, we have N ( ,F , d[Pz̄,Gnl ]) ≤ max1≤j≤nN ( ,F , d[Pz̄;j ,Gl]), and N ( ,Gnl , 2m) ≤ N ( ,Gl, 2m)n.
Recalling Theorem 3 and Propositions 1-2, we can further establish the following covering number bound for meta learning with the representation learning.
Theorem 4 Let (P, Q) be an almost Π-related environment on the complete separable metric space Z = X × Y . Let H = {H} be the set of hypothesis spaces of the form H = G◦f , f ∈ F . Then for anyH ∈ H, any 0 < < 1, with probability at least 1− δ over z, we have
|êrz(H)− erQ(H)| ≤ √ 64
mn ln
4 δ +
√ 64
mn
( max
1≤j≤n lnN ( 8 ,F , d[Pz̄;j ,Gl]) + n lnN ( 8 ,Gl, 2m) ) We need to highlight the important role of Theorem 4: the covering number of the hypothesis space family Hnl = Gnl ◦F for meta learning (over n 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 Gl 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 2). In particular, by bounding the covering number in Theorem 4 with the Lipschitz constants of the function in each layer of the deep neural network, we can achieve non-parameter-count-based bounds (or say norm-constraint-based bounds (Neyshabur et al., 2017)) for meta learning, which will be detailed in the next section.

heading: 4.3 SPECTRALLY-NORMALIZED BOUNDS FOR META LEARNING WITH NEURAL NETWORK
text: Based on the theoretical results in Section 4.2, we now aim to derive non-parameter-count-based spectrally-normalized 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 : Rd0 → Rd, where d0, d are the dimension of input data and embedded feature, respectively. Each layer of the network has a weight matrix Ai and a ρi-Lipschitz nonlinearity σi, with σi(0) = 0 . Then the composition function is given as
σi◦Ai : Rdi−1 → Rdi , ∀i ∈ [L]. For anyA = (A1, · · · , AL), any input data x ∈ X , define fA(x) = σL(ALσL−1(AL−1 · · ·σ1(A1x) · · · )) ∈ Rd. Let F denote the class of functions computed by the corresponding networks, and D the maximum of {d0, d1, ..., dL−1, d}. Further, define a sequence of reference matrix (M1, ...,ML) with the same dimensions as (A1, ..., AL), where Mi = 0 in AlexNet (Krizhevsky et al., 2012) and Mi = I in ResNet (He et al., 2016) to ensure good generalization performances. Let ‖·‖σ denote the spectral norm, and let ‖·‖p,q denote the (p, q)-norm defined by ‖A‖p,q =
∥∥(‖A;1‖p, ..., ‖A;k‖p)∥∥q for matrix A ∈ Rd×k. We next give a spectrally-normalized meta-learning bound with deep neural network. For the ease
of presentation, we bound O( √
C1+nC2 nm ) with O( √ C1 nm + √ C2 m ).
Theorem 5 Let (P, Q) be an almost Π-related environment on the complete separable metric space Z = X×Y . Let H = {HA} = {G◦fA : fA ∈ F ,A = (A1, ..., AL), ‖Ai‖σ ≤ si, ‖A>i −M>i ‖2,1 ≤ bi, i ∈ [L]} be a hypothesis space family where each HA is of the form HA = G◦fA = {g◦fA(·) : g = σ◦W,W ∈ Rk×d, ‖W>‖2,1 ≤ θ}, where σ is an element-wise function with Lipschitz constant θσ . Suppose that ∃b > 0, for any x ∈ X ⊆ Rd0 , ‖x‖2 ≤ b. Suppose that the loss function l satisfies two conditions: (1) when composed with g, gl(·, y) is an α-Lipschitz function w.r.t. the norm ‖·‖2, ∀ fixed y ∈ Y ; (2) ∀ fixed v ∈ Rd, fixed y ∈ Y , ∀g = σ◦W, g′ = σ◦W ′ ∈ G, ∃β > 0, such that |gl(v, y) − g′l(v, y)| ≤ β‖Wv −W ′v‖2. Then for any HA ∈ H, for any 0 < < 1/8, with probability at least 1− δ over z, we have
|êrz(HA)− erQ(HA)|≤ √ 64
mn ln
4 δ +
8b ∏L l=1slρl
√ mn
[ α √ ln (2D2) ( L∑ i=1 ( bi si ) 2 3 ) 3 2 +βθ √ n ln (2dk) ] .
When the loss function l(·, y) is a γ-Lipschitz function w.r.t. the norm ‖·‖2, we can set α = γθσθ, β = γθσ . 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 1 of Appendix B that the above bound is informative for two-layer neural network.

heading: 4.3.1 A SPECTRALLY-NORMALIZED BOUND FOR BINARY CLASSIFICATION
text: 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 applicability in binary classification scenarios. Formally, let G = {σ◦w : w ∈ Rd, ‖w‖1 ≤ θ} 5 be the class of prediction functions, where σ is the sigmoid activation function σ(v) = 11+e−v (∈ [0, 1]). Let gl◦f(x, y) = gl(v, y) be the loss function on (x, y) where gl(v, y) = −y ln(σ(w>v)) − (1 − y) ln(1− σ(w>v)) is the cross-entropy loss. We then have the following claim.
Claim 1 In the binary classification problem as described above, ∀y ∈ Y , gl(·, y) is a 2θ-Lipshcitz function w.r.t. l2-norm. Further, fix v ∈ Rd, y ∈ {0, 1}, then we have ∀w1, w2 ∈ Rd, |l(w>1 v, y) − l(w>2 v, y)| ≤ 2|w>1 v − w>2 v|. Thus, we can set α = 2θ, β = 2 in Theorem 5 to obtain a spectrallynormalized bound for binary classification with logistic regression model in meta learning.

heading: 4.3.2 A SPECTRALLY-NORMALIZED BOUND FOR MULTICLASS CLASSIFICATION
text: We further consider the multiclass classification problem under the meta learning framework, where Y = {1, ..., k}(k ≥ 3). Let G = {W ∈ Rk×d : ‖W>‖2,1 ≤ θ} be the class of prediction functions, and Φρ◦M(g◦f(x), y)(f ∈ F , g ∈ G) be the loss on (x, y). Φρ(v) = min ( 1,max(0, 1 − vρ ) ) is called the margin loss and ρ is a positive margin parameter. M(g◦f(x), y) = maxj 6=y g◦f(x)[j]− g◦f(x)[y] 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 ∈ Y , the loss function l(·, y) = Φρ◦M(·, y) is 2/ρ-Lipschitz w.r.t. the norm ‖·‖2. Then we can set γ = 2/ρ and θσ = 1 (σ is the identity map in this case) in Theorem 5 and derive a spectrally-normalized margin bound for multiclass classification in meta learning.
5In the binary classification, HA = G◦fA can be considered as the set of the functions from X → R (not X → Y = {0, 1}), but the loss functions erQ(HA) and êrz(HA) are still well-defined. We use this notation just for simplicity and concision. Similar treatment can also be found in the multiclass classification problem.

heading: 4.3.3 A SPECTRALLY-NORMALIZED BOUND FOR REGRESSION
text: For completeness, we finally consider the regression problem under the meta learning framework, where Y = [0, 1]. Let G = {σ◦w : w ∈ Rd, ‖w‖1 ≤ θ} be the class of prediction functions, where σ is the sigmoid activation function σ(v) = 11+e−v (∈ [0, 1]) with the Lipschitz constant 1/4 (note that the derivative σ′(v) = σ(v)(1 − σ(v)) ≤ 1/4). Let the loss function l be the squared loss function by defining gl◦f(x, y) = (σ(w>f(x))− y)2(f ∈ F , g ∈ G).
Claim 3 In the regression problem as described above, for any y ∈ Y , the loss function l(·, y) is 2-Lipschitz w.r.t.‖·‖2. Then we can set γ = 2 and θσ = 1/4 (σ is the sigmoid function in this case) in Theorem 5 and derive a spectrally-normalized bound for regression problem in meta learning.

heading: 4.4 WHEN THE ENVIRONMENT IS ALMOST Π-RELATED?
text: In this section, we explore when the given environment (P, Q) is almost Π-related, i.e., whether there exists a common underlying distribution P that is almost Π-related with any measure Pi sampled 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, 2007)). We first give the definition of the almost isomorphism and the proof of Theorem 6 can be found in the Appendix.
Definition 7 (Almost Isomorphism) Let (Z1,A, µ) and (Z2,B, ν) be two measure spaces. (1) A point isomorphism π of these spaces is a one-to-one mapping ofZ1 on toZ2 such that µ◦π−1 = ν and π(A) = B. That is, ∀A ∈ A, π(A) ∈ B, and vice versa. (2) (Z1,A, µ) and (Z2,B, ν) are called almost isomorphic if there exist sets N1 ∈ Aµ, N2 ∈ Bν with µ(N1) = ν(N2) = 0 and a point isomorphism π of the spaces Z1\N1 and Z2\N2 that are equipped with the restriction of the measures µ and ν and the complete σ-algebra Aµ and Bν .
With elaborate 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 Π-related to any distribution sampled from the same environment. It is formally stated as below.
Theorem 6 Let (P, Q) be an environment on the complete separable metric space Z. Then for any atomeless Pi, Pj ∈ P(i 6= j, i, j ∈ I), the probability measure spaces (Z,Bi, Pi) and (Z,Bj , Pj) are almost isomorphic. In other words, the two measures Pi and Pj are almost Π-related.
From Theorem 6 we have seen that, any two atomless probability measures Pi, Pj(i 6= j) on the complete separable metric space Z are almost Π-related. Therefore, we can choose P1 ∈ P as the common distribution that is almost Π-related to any probability measure Pi(i ∈ I) sampled from the set P . Hence, we demonstrate the existence of the common distribution P defined in Definition 5. Further, we can drop the condition of the Π-relatedness of all tasks sampled from the environment (P, Q) in Theorems 2-5, 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 a number of metric spaces such as the real space Rd, the closed subspace in Rd, and the product space of the complete separable metric spaces. For example, in d-dimensional regression problem, the sample space Z = Rd× [a, b] (a, b ∈ R) is also a complete separable metric space.

heading: 5 CONCLUSIONS
text: This paper provides a covering number based generalization bound for meta learning by exploiting the task relatedness of the environment. When analyzing the meta learning with deep neural network, we derive spectrally-normalized bounds for classification and regression problems. Our bounds rely on two basic assumptions: the relatedness between different tasks and the closure property 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 as their equivalent variants. Our ongoing research includes analyzing the convolutional neural network as well as establishing sharper generalization bounds for meta learning via algorithmic analysis.

heading: ACKNOWLEDGEMENTS
text: Jiechao Guan sincerely thanks Dr. Qi Meng from MSRA for helpful discussions and insightful comments on the writing of this paper. We thank anonymous reviewers for spotting a mistake in the original proof of this paper. We also thank all reviewers for their constructive suggestions to improve the quality of this paper. This work was supported in part by National Natural Science Foundation of China (61976220 and 61832017), Beijing Outstanding Young Scientist Program (BJJWZYJH012019100020098), China Unicom Innovation Ecological Cooperation Plan, and Large-Scale Pre-Training Program 468 of Beijing Academy of Artificial Intelligence (BAAI).

heading: A MOTIVATION OF TASK RELATEDNESS
text: We simply explain our motivation of exploring ‘task relatedness’ by comparing the differences between single task learning and meta learning in Table 1, 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 erQ(H) − erz(H) = ∫
infh∈H erP (h)dQ(P ) −∑n
i=1 infh∈H êrPi(h). The proposal of our task relatedness notion comes from the motivation that probabilities measures {Pi}ni=1 sampled from the environment (P,Q) need to be equivalent, namely, almost Π-related.
Setting Single-Task Learning Meta-Learning Goal choose hypothesis h ∈ H choose hypothesis spaceH ∈ H Dealing Objective i.i.d. sample ~z = {zi}mi=1 i.i.d. probability measures {Pi}ni=1 Generalization Gap erP (h)− êr~z(h) erQ(H)− erz(H) Requirement {zi}mi=1 are similar enough i.e.,
identical distributed samples. {Pi}ni=1 need to be similar enough i.e., equivalent measures.

heading: B DETAILED PROOFS OF OUR THEORETICAL RESULTS
text: B.1 PROOF OF THEORETICAL PROPERTIES OF ALMOST Π-RELATED ENVIRONEMENT
Proof of Lemma 1 in the main paper. From Definition 3, ∃Ni ⊆ Z, such that Pi(Ni) = 0. Then for any P -measurable set A ⊆ Z\N ,
P (A)= ∫ Z 1A∩(Z\N) + 1A∩NdP = ∫ Z\N 1AdP
= ∫ Z\Ni 1πi(A)dPi= ∫ Z 1πi(A)dPi= ∫ Z 1A◦π −1 i dPi = ∫ Z 1AdPi◦πi=Pi(πi(A)),
where the third equality holds due to the condition (3) in Definition 3, and the sixth equality holds due to the equivalent integral transformation ∫ f◦g−1dP = ∫ fdP ◦g. Similarly, recalling P (hl) from Definition 1 and noticing π−1i (Ni) is P -measurable from condition (4) in Definition 3, we have
Pi(hl◦π −1 i )=( ∫ Z\Ni + ∫ Ni )hl◦π −1 i dPi = ∫ Z\N hldP = P (hl).
The above second equality holds due to the fact that ∫ Ni hl◦π −1 i dPi = 0 (since Pi(Ni) = 0 and hl is a bounded function), and the condition (3) of π−1i in Definition 3.
Proof of Lemma 2 in the main paper. To prove infh∈H erP (h) = infh∈H erPi(h), it is equivalent to prove infhl∈Hl P (hl) = infhl∈Hl Pi(hl), then it suffices to show that ∀hl ∈ Hl, ∃h′l ∈ Hl we have Pi(h′l) ≤ P (hl). Since the symmetricity of P and Pi (i.e., P ◦π−1i = Pi, Pi◦πi = P holds almost everywhere), we can find another h′′l such that P (h ′′ l ) ≤ Pi(hl). In fact, let h′l = hl◦π −1 i , from Lemma 1, we have Pi(h ′ l) ≤ P (hl).
B.2 PROOF OF THE COVERING NUMBER BOUND FOR META LEARNING IN ALMOST Π-RELATED ENVIRONMENT
Lemma 3 (Theorem 18 in (Baxter, 2000)) LetH ⊆ H1⊕· · ·⊕Hn be a permissible class of functions mapping (X × Y )n into [0, 1]. Let z ∈ (X × Y )(m,n) be generated by m ≥ 2/( 2ν) independent
trials from (X × Y )n according to some product probability measure P = P1 × · · · × Pn. For any ν > 0, 0 < < 1, for any h ∈ H, we have
Pr{z ∈ (X × Y )(m,n) : sup H dν [êrz(h), erP(h)] > } ≤ 4N ( ν/8,H,dz̄) exp(− 2νmn/8).
Proof of Theorem 1 in the main paper.
Pr{z ∈ (X × Y )(m,n) : sup H dν [êrz(H), êrP(H)] > }
≤ Pr{z ∈ (X × Y )(m,n) : sup Hnl dν [êrz(h), erP(h)] > }
≤ 4N ( ν/8,Hnl ,dz̄) exp(− 2νmn/8), where the first inequality holds due to the Lemma 24 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 δ ∈ (0, 1), then we have 2 ≥ 8νmn ln 4N ( ν/8,Hnl ,dz̄) δ , which gives the explicit PAC-style generalization bound on dν [êrz(H), êrP(H)] in Theorem 1. Proof of Theorem 2 in the main paper. According to Lemma 2, there exists a common distribution P ∈ P such that erP (H) = erPi(H) for any Pi ∈ P . Then erQ(H) = ∫ P erPi(H)dQ(Pi) = ∫ P erP (H)dQ(Pi) = erP (H) =
1/n ∑n j=1 erPj (H) = êrP(H), which indicates |erQ(H)− êrP(H)| = 0.
Proof of Theorem 3 in the main paper. By the fact that the loss function l has range [0, 1], and the triangle inequality of metric dν ,
|êrz(H)− erQ(H)| ν + 2 ≤ dν [êrz(H), erQ(H)]
≤ dν[êrz(H), êrP(H)] + dν[êrP(H),erQ(H)] ≤ √ 8
νmn ln 4N ( ν/8,Hnl ,dz̄) δ .
Letting ν = 2 (to minimize √ ν + 2√
ν ) gives the result.
B.3 PROOF OF COVERING NUMBER BOUNDS FOR META LEARNING WITH REPRESENTATION LEARNING
Proof of Proposition 1 in the main paper. Fix an empirical measure Pz̄ on (X ×Y )n, and let F̂ be a minimum size 1-cover for (F , d[Pz̄,Gnl ]), then we have |F̂ | = N ( 1,F , d[Pz̄,Gnl ]), and ∀f̄ ∈ F ,∃f̂ ∈ F̂ such that d[Pz̄,Gnl ](f̄, f̂) ≤ 1. For any f̂ ∈ F̂ , let Pz̄◦f̂−1 be the induced probability measure on (V × Y )n by defining Pz̄◦f̂−1(A) = Pz̄(f̂−1(A)),∀A ∈ σ-algebra on (V × Y )n. Let Gf̂ be the minimum size 2-cover for (Gnl , dPz̄◦f̂−1). Hence |Gf̂ | = N ( 2,G n l , dPz̄◦f̂−1) ≤ N ( 2,G n l , 2m). Let N = {g◦f : f ∈ F̂ and g ∈ Gf}, then we have |N | ≤ N ( 1,F , d[Pz̄,Gnl ])N ( 2,G n l , 2m), which satisfies the required cardinality condition. It remains to show that N is an 1 + 2−cover of Hnl . Actually, ∀g1 ⊕ · · · ⊕ gn◦f̄ ∈ Hnl , choose f̂ ∈ F̂ such that d[Pz̄,Gnl ](f̄, f̂) ≤ 1, and choose g ′ 1 ⊕ · · · ⊕ g′n ∈ Gf̂ such that dPz̄◦f̂−1(g1 ⊕ · · · ⊕ gn, g ′ 1 ⊕ · · · ⊕ g′n) ≤ 2. Then the triangle inequality of the distance metric dz̄ implies that
dz̄(g1 ⊕ · · · ⊕ gn◦f̄, g′1 ⊕ · · · ⊕ g′n◦f̂) ≤dz̄(g1 ⊕ · · · ⊕ gn◦f̄, g1 ⊕ · · · ⊕ gn◦f̂) + dz̄(g1 ⊕ · · · ⊕ gn◦f̂, g′1 ⊕ · · · ⊕ g′n◦f̂) ≤d[Pz̄,Gnl ](f̄, f̂) + dPz̄◦f̂−1(g1 ⊕ · · · ⊕ gn, g ′ 1 ⊕ · · · ⊕ g′n) ≤ 1 + 2.
The second inequality holds due to the definition of d[Pz̄,Gnl ](f̄, f̂) = 1/2m ∑2m i=1 supg∈Gnl |g◦f̄(z̄i) − g◦f̂(z̄i)| and the equivalent integral transformation∫
gdPz̄◦f̂−1 = ∫ g◦f̂dPz̄, ∀g ∈ Gnl .
Proof of Proposition 2 in the main paper. For any f̄, f̄ ′ ∈ F , we have
d[Pz̄,Gnl ](f̄, f̄ ′) =
1
2m 2m∑ i=1 sup g∈Gnl |g◦f̄(z̄i)− g◦f̄ ′(z̄i)|
= 1
2m 2m∑ i=1 sup Gnl | 1 n n∑ j=1 gj◦f(zij)− gj◦f ′(zij)|
≤ 1 n n∑ j=1 1 2m 2m∑ i=1 sup gj∈Gl |gj◦f(zij)− gj◦f ′(zij)|
≤ max 1≤j≤n d[Pz̄;j ,Gl](f, f ′),
which completes the proof of the first inequality. Similarly, for the second one, ∀P ∼ Qn, s ∼ P 2m,∀g, g′ ∈ Gnl ,
dPs(g, g ′) =
1
2m 2m∑ i=1 |g(si)− g′(si)|
= 1
2m 2m∑ i=1 | 1 n n∑ j=1 gj(vij , yij)− g′j(vij , yij)|
≤ 1 n n∑ j=1 1 2m 2m∑ i=1 |gj(vij , yij)− g′j(vij , yij)|
≤ max 1≤j≤n
1
2m 2m∑ i=1 |gj(vij , yij)− g′j(vij , yij)|
= max 1≤j≤n
dPs;j (gj , g ′ j).
Therefore, N ( ,Gnl , dPs) ≤ ( max1≤j≤nN ( ,Gl, dPs;j ) )n
and thus N ( ,Gnl , 2m) ≤ N ( ,Gl, 2m)n.
B.4 PROOF OF SPECTRALLY-NORMALIZED BOUNDS FOR META LEARNING WITH DEEP NEURAL NETWORK
To demonstrate Theorem 5 in the main paper, we need to give the following two important lemmas, which gives the non-parameter-count-based spectrally-normalized bounds for deep neural network in the single task learning.
Lemma 4 (Bartlett et al., 2017) Let positive reals (α, β, ) and positive integer k be given. Let matrix V> ∈ R2m×d be given with ‖V>‖2 ≤ β. Then
N ({V>A : A ∈ Rd×k, ‖A‖2,1≤α}, , ‖·‖2)≤(2dk)d α2β2 2 e.
Lemma 5 (Bartlett et al., 2017) Let fixed nonlinearities (σ1, ..., σL) and reference matrices (M1, ...,ML) be given, where σi is ρi-Lipschitz and σi(0) = 0. Let spectral norm bounds (s1, ..., sL), and matrix (2, 1)-norm bounds (b1, ..., bL) be given. Let the input data matrix X ∈ R2m×d0 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 fA : HX = {fA(X>)|A =
(A1, ..., AL), ‖Ai‖σ ≤ si, ‖A>i − M>i ‖2,1 ≤ bi}, where each matrix has dimension at most D along each axis. Then for any > 0,
lnN (HX, ,‖·‖2)≤ ‖X‖22 ln (2D2) 2 ( L∏ j=1 s2jρ 2 j )( L∑ i=1 ( bi si ) 2 3 )3
Proof of Theorem 5 in the main paper. First, we bound lnN ( ,F , d[P~z,Gl]). For any P ∈ P, ~z ∼ P 2m, for any fA, fA′ ∈ F ,
d[P~z,Gl](fA, fA′) = 1
2m 2m∑ i=1 sup gl∈Gl |gl◦fA(zi)− gl◦fA′(zi)|
= 1
2m 2m∑ i=1 sup gl∈Gl |gl(fA(xi), yi)− gl(fA′(xi), yi)|
≤ α 2m 2m∑ i=1 ‖fA(xi)− fA′(xi)‖2 (Lipschitz) ≤ α√ 2m ‖fA(X>)− fA′(X>)‖2. (Jensen)
Applying Lemma 5, we then have
lnN ( ,F , d[P~z,Gl]) ≤ lnN ( √ 2m
α ,F , ‖·‖2)
≤α 2‖X‖22 ln (2D2) 2m 2 ( L∏ j=1 s2jρ 2 j )( L∑ i=1 ( bi si ) 2 3 )3 ≤ α2b2 ln (2D2) 2 ( L∏ j=1 s2jρ 2 j )( L∑ i=1 ( bi si ) 2 3 )3 . (1)
Next, we bound lnN ( ,Gl, dP~s). Actually, for any P ∼ Q,~s ∼ P 2m, for any gl, g′l ∈ Gl, using condition (2) of the loss function l and Jensen inequality, we have
dP~s(g, g ′) =
1
2m 2m∑ i=1 |gl(vi, yi)− g′l(vi, yi)|
≤ β 2m 2m∑ i=1 ‖Wvi −W ′vi‖2 ≤ β√ 2m ‖V>W> −V>W ′>‖2,
where V = (v1, ..., v2m) ∈ Rd×2m. Then combining the above results and Lemma 4, we have lnN ( ,Gl, dP~s)
≤ lnN ( √ 2m
β , {V>W> : ‖W>‖2,1 ≤ θ}, ‖·‖2)
≤ β 2θ2‖V>‖22
2m 2 ln (2dk) ≤
β2θ2b2 ∏L l=1 s 2 l ρ 2 l
2 ln (2dk).
(2)
The last inequality holds due to the Lipschitz property of the activation σl and the matrix Al(l = 1, ..., L), ∀i ∈ [2m]
‖vi‖2 = ‖σL(AL · · ·σ1A1(xi) · · · )− σL(0)‖2
≤sLρL‖σL−1(AL−1 · · ·σ1A1(xi) · · · )‖2 ≤ b L∏ l=1 slρl.
Recalling Theorem 4 in the main paper and Eqs.(1)-(2) in the supplementary gives the result.
Remark 1 (A situation where our spectrally-normalized bound for meta-learning is informative) We further provide a situation where the neural network is a two-layer network (i.e. composed of a
hidden layer with D units and an output layer) for k-class classification problem, to provide more information of our spectrally-normalized bound from two aspects: (i) Our bound in Theorem 5 is more informative than the traditional VC-dimension bound. Actually, our bound in Theorem 5 for two-layer network can be rewritten as follow:√
64
mn ln
4 δ + 8bs1ρ1 √ mn
[ α √
ln (2D2)( b1 s1
) + βθ √ n ln (2dk) ] ,
which is of order O( b1 √
lnD2√ nm
+ s1 √
ln (Dk)√ m
). Under the same setting, the VC-dimension based meta-learning bound for neural networks (i.e. obtained with techniques from Theorem 8 in Baxter (2000)) is of order O( v√
nm + v√ m ). Further note that the VC-dimension of the neural networks
is v = W lnW (where W is the total number of the parameters, see Bartlett et al. (2019)), thus the VC-dimension for two-layer neural networks is about v = (D2 + Dk) ln (D2 +Dk) and the meta-learning bound is about O( (D
2+Dk) ln (D2+Dk)√ nm + (D 2+Dk) ln (D2+Dk)√ m ), which is looser than
our spectrally-normalized meta-learning bound of O( b1 √
lnD2√ nm
+ s1 √
ln (Dk)√ m
). (ii) Our bound in 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 et al. (2017)), therefore the norm parameters s1 and b1 in our bound for two-layer neural networks can be small, and hence our spectrally-normalized meta-learning bound of order O( b1 √
lnD2√ nm
+ s1 √
ln (Dk)√ m ) can be informative.
Proof of the Corollary under Theorem 5 in the main paper. ∀v1, v2 ∈ Rd, ∀y ∈ Y ,
|gl(v1, y)− gl(v2, y)| = |l(g(v1), y)− l(g(v2), y)| =|l(σ◦Wv1, y)− l(σ◦Wv2, y)| ≤ γθσ‖Wv1 −Wv2‖2 ≤ γθσθ‖v1 − v2‖2,
where the second inequality holds since ‖W>‖2,1 is a kind of matrix norm of W . Hence we can set α = γθσθ. Similarly, ∀gl, g′l ∈ Gl, v ∈ Rd, y ∈ Y , we have |gl(v, y)− g′l(v, y)|
= |l(σ◦Wv, y)− l(σ◦W ′v, y)| ≤ γθσ‖Wv −W ′v‖2.
Then we can obtain β = γθσ . Combining the above results with Theorem 5 gives the result.
Proof of Claim 1 in the main paper. ∀v ∈ Rd, gl(v, y) = −y ln(σ(w>v))− (1− y) ln(1− σ(w>v)). Therefore, ∀v1, v2 ∈ Rd, we have
|gl(v1, y)− gl(v2, y)|
=|y(w>v2 − w>v1) + ln 1 + ew
>v1
1 + ew>v2 |
≤|w>v2 − w>v1|+ | ln 1 + ew
>v1
1 + ew>v2 |
≤2|w>v2 − w>v1| (ln(1 + ex) is 1− Lipschitz) ≤2θ‖v2 − v1‖2 (Schwarz and ‖w‖2 ≤ ‖w‖1).
Similarly, since l(w>v, y) = −y ln(σ(w>v))− (1− y) ln(1− σ(w>v)), for any y ∈ {0, 1} we can obtain
|l(w>1 v, y)− l(w>2 v, y)| = |y(w>1 v − w>2 v) + ln 1 + ew
> 2 v
1 + ew > 1 v | ≤ 2|w>1 v − w>2 v|.
Proof of Claim 3 in the main paper. For any fixed y ∈ [0, 1], for any v1, v2 ∈ Rd, notice that both g(v1) and g(v2) also lie into the interval [0, 1], then
|l(g(v1), y)− l(g(v2), y)| = |(g(v1)− y)2 − (g(v2)− y)2| ≤ 2|g(v1)− g(v2)|.
B.5 PROOF OF WHEN THE ENVIRONMENT IS ALMOST Π-RELATED?
To obtain a complete proof of Theorem 6 in the main paper, we 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 7 (Bogachev, 2007) Let (Z, µ) be a complete separable metric space with a Borel probability measure µ. Then (Z, µ) is almost isomorphic to the space ([0, 1], ν), where ν is some Borel probability measure. If µ is 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) = µ(A4B), A,B ∈ 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) = 0. Then the metric space (B/µ, d) is called the metric Boolean algebra, or measure algebra, often denoted by Eu.
Further, the metric space (B/µ, d) is separable,i.e.,contains a countable everywhere dense subset, if and only if the corresponding measure µ is separable. The separability of µ is equivalent to the existence of a countable collection of sets Bn ∈ B such that ∀B ∈ B and > 0, there exists an integer n with µ(B4Bn) ≤ . In addition, a metric space (B/µ, d) is complete if B is a σ-algebra and µ is countably additive (e.g., µ is a measure).
Definition 9 (Metric Boolean Isomorphism) Two measure algebrasEu1 andEu2 generated by measure spaces (Z1,B1, µ1) and (Z2,B2, µ2) are called isomorphic if there exists a one-to-one mapping J from Eµ1 onto Eµ2 (called a metric Boolean isomorphism) such that J preserves the measure, i.e., µ2(J (A)) = µ1(A),∀A ∈ Eµ1 .
Theorem 8 (Bogachev, 2007) Every separable atomless measure algebra is isomorphic to the measure algebra of some interval (e.g., [0,1]) with Lebesgue measure.
Definition 10 (Lebesgue-Rohlin Space) A measure space (Z,B, µ) is called a Lebesgue-Rohlin space if it is almost isomorphic to some measure space (Z ′,B′, µ′) with a countable basis with respect to which Z ′ is complete.
Example 1 The space ([0, 1],B([0, 1]), λ), where λ is Lebesgue measure, has a countable basis with respect to which it is complete.
Theorem 9 (von Neumann, 1932) Let (Z1,B1, µ1) and (Z2,B2, µ2) be Lebesgue-Rohlin spaces with probability measures. If the corresponding measure algebraEµ1 andEµ2 are isomorphic in the sense of Definition 9, then there exists an almost isomorphism between these spaces. In particular, this is the case if both measures are atomless.
Proof of Theorem 6 in the main paper. The proof contains 3 main steps: (1) Since Z is the complete separable metric space and the probability measures Pi, Pj are atomless, then from Theorem 7, (Z,Bi, Pi) and (Z,Bj , Pj) are both almost isomorphic to the measure space ([0, 1],B([0, 1]), λ) where λ is the Lebesgue measure. From Definition 10 and Example 1, (Z,Bi, Pi) and (Z,Bj , Pj) are Lebesgue-Rohlin spaces. (2) From Example 1, the complete measure space ([0, 1]\M,B([0, 1])λ, λ) (w.r.t. the measure λ and λ(M) = 0) has a countable basis {Bn}∞n=1 ⊂ B([0, 1])λ. The almost isomorphism πi from ([0, 1],B([0, 1]), λ) into (Z,Bi, Pi) can induce a countable basis {πi(Bn)}∞n=1 ⊂ Bi, which guarantees the separability of the measure algebras EPi . The separability of the measure algebras EPj can be guaranteed in the same way. Then from Theorem 8, the measure algebras EPi and EPj , generated by measure spaces (Z,Bi, Pi) and (Z,Bj , Pj) , are both isomorphic to the measure algebra of the interval [0,1] with Lebesgue measure. Therefore, the two measure algebra EPi and EPj are isomorphic (since isomorphism is an equivalence relation). (3) Combining (1) and (2), and recalling Theorem 9, the two measure spaces (Z,Bi, Pi) and (Z,Bj , Pj) are almost isomorphic. So Pi and Pj are almost Π-related in the sense of Definition 3.

heading: C MORE DETAILED COMPARISONS WITH RELATED WORKS
text: C.1 DETAILED COMPARISON WITH GENERALIZATION BOUNDS OF (BAXTER, 2000)
This paper can be considered as the extension of the meta learning theoretical work in (Baxter, 2000), by further exploring the task relatedness for the environment. In this section, we detail our improvements over this pioneering work. First, we introduce a new notation called H∗. For any hypothesis space H ∈ H, define H∗ : P → [0, 1] by H∗(P ) = infh∈H erP (h), and for any hypothesis space family H, define H∗ = {H∗ : H ∈ H}. Although Baxter does not give the explicit PAC-style learning bound in his main paper, its bound on |êrz(H)− erQ(H)| can be expressed as:√
64
mn ln 8C( /8,Hnl ) δ +
√ 64
n ln 8C( /8,H∗) δ , (3)
where C( ,Hnl ) = supPN ( ,Hnl ,dP), C( ,H∗) = supQN ( ,H∗,dQ) (see its Theorem 4). Our improvements can be summarized in the following three aspects: (1) We exploit the proposed task relatedness to reduce the complexity C( ,H∗) in Eq. (3) to zero in Theorems 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 Z to be a separable metric space to obtain theoretical results, our derived meta learning bound in Theorem 3, albeit depending on a slightly stronger assumption, is a non-trivial enhancement. Nevertheless, we admit that our results also rely on the closure property of the function classHl. (2) Our covering number results (e.g., Theorem 4) are based on the metric defined w.r.t. the empirical measure, instead of the abstract measure in Baxter’s work (e.g., Theorem 6 in (Baxter, 2000)). 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. (3) When bounding the covering number (or say capacity) of the neural network C( 2,F) (i.e., Theorem 8 in (Baxter, 2000)), Baxter uses traditional Pseudo-dimension indicator which is developed by (Haussler, 1992), resulting in a parameter-count-based bounds for meta learning with neural network. 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-3 are all independent of the size of total parameters, outperforming the results in Theorem 8 of (Baxter, 2000).
Remark 2 (The three main technical difficulties when applying spectrally-normalized margin bounds for meta-learning with deep neural networks) Now, we give more explanations about the three main technical difficulties when applying spectrallynormalized margin bounds (Bartlett et al., 2017) for meta-learning with deep neural networks. (i) We need to remove the second covering number complexity (i.e. the covering number complexity ofH∗) in the meta-learning bound in Eq. (3) in Section C.1 (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 Definitions 3-4 in (Baxter, 2000)), we cannot use any modern theoretical results in deep learning (e.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-based bounds for deep neural networks. The aforementioned challenge motivated us to propose the Π-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 distance 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 1-2 (also see our Definition 6), hence we can extend our generalization bound in Theorem 3 to the representation setting and make our meta-learning bound with representation learning (i.e. our Theorem 4) much easier 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 to connect the covering number complexity in meta-learning setting (e.g.
see our Definition 6, w.r.t. the empirical measure) with the spectrally-normalized based covering number complexity from Bartlett et al. (2017) (i.e. Lemmas 4-5 in our Appendix B.4). Such difficulty is overcome by using the Lipschitness property of neural networks and the theoretical properties of covering number (see the proof of Theorem 5 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 Π-relatedness notation and the task relatedness notion defined in (Ben-David & Schuller, 2003). We first recall this previous concept in (Ben-David & Schuller, 2003, Definition 2.1).
Definition 11 (Ben-David & Schuller, 2003) Let F be a set of transformations f : X → X , and let P1, P2 be probability distributions over X × {0, 1}. We say that P1, P2 are F-related distributions if there exists some f ∈ F such that for any T ⊂ X × {0, 1}, T is P1-measurable iff f [T ] = {(f(x), b)|(x, b) ∈ T} is P2-measurable and P1(T ) = P2(f [T ]).
Remark 3 (The main differences between our task relatedness notation and that of (Ben-David & Schuller, 2003)) Note that in Definition 11, the condition P1(T ) = P2(f [T ]) means that P1(T ) = P2 ◦ (f × I)[T ] for all T ⊂ X × {0, 1}. Therefore P1 = P2 ◦ (f × I) and hence f × I is a (bijective) measurepreserving transformation on the product space X × {0, 1}. Recall the definition of our proposed task relatedness concept in Definition 3 in the main paper. It’s not difficult to see that there are two main differences between these two task-relatedness notions: (i) The bijective transformation f in Definition 11 of David’s work is 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 × Y ) and the sample space Z. Note that the bijective transformation f in Definition 11 can be viewed as the bijective transformation f×I on the product spaceX×Y , where I is the identity map on the output space Y . Therefore the transformation given by (Ben-David & Schuller, 2003) can be considered as a special case of our proposed task-relatedness concept. (ii) Furthermore, the bijective transformation f given in Definition 11 is a function map imposed on the whole input space X , whereas our proposed bijective transformation π is imposed on the almost whole sample space Z excluding a measure-zero set. In other words, our proposed π is a bijective map between Z\N and Z\N1, where N,N1 are P -measure zero and P1-measure zero sets, respectively. Such design will allow more flexibility of the choice of the bijective map π, and can help us theoretically guarantee the existence of the almost bijective function on the whole sample space Z (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 × I is a measure-preserving bijective on the product space 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-relatedness concept, the explicit form of the bijective transformation π in Theorem 6 of main paper can be found in (Bogachev, 2007, Theorem 6.5.7). In that result, Bogachev takes π as the composition of functions ∑∞ n=1 IEn and ( ∑∞ n=1 IBn)
−1, where En belongs to the σalgebra Bµ over the sample space Z associated with the measure µ, Bn belongs to the σ-algebra Bν over the sample spaceZ associated with the measure ν, I is the indicator function from the σ-algebra over Z to the interval [0, 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 × Y = Rd ×R, the focused measure is Lebesgue measure and the bijective function π : π(~z) = ~z + ~a,~a ∈ Z is a translation over high-dimensional Euclidean space.

Review summaries:
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.

The paper: 1) 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. 2) 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. 3) They demonstrate that any two tasks in the environment are almost $\Pi$-related if the focused sampled space is a complete separable metric space.

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

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