Title: LOCALIZED META-LEARNING: A PAC-BAYES ANAL-YSIS FOR META-LEARNING BEYOND GLOBAL PRIOR

Abstract: Meta-learning methods learn the meta-knowledge among various training tasks and aim to promote the learning of new tasks under the task similarity assumption.
However, such meta-knowledge is often represented as a fixed distribution, which is too restrictive to capture various specific task information. In this work, we present a localized meta-learning framework based on the PAC-Bayes theory. In particular, we propose an LCC-based prior predictor that allows the meta learner to adaptively generate local meta-knowledge for specific tasks. We further develop a practical algorithm with deep neural network based on the bound. Empirical results on real-world datasets demonstrate the efficacy of the proposed method.
Under review as a conference paper at ICLR 2020 approaches (Lever et al., 2013) . Thus, choosing an appropriate prior for each task which is close to the related posterior could yield improved generalization bounds.
Inspired by this, we propose a Localized Meta-Learning (LML) framework. Instead of formulating meta-knowledge as a global hyperposterior, we learn a conditional hyperposterior given task data distribution that allows a meta learner to adaptively generate an appropriate prior for a new task.
However, the task data distribution is unknown, and our only perception for it is via the associated sample set. Nevertheless, if the conditional hyperposterior is relatively stable to perturbations of the sample set, then the generated prior could still reflect the underlying task data distribution, resulting in a generalization bound that still holds with smaller probability. Following this intuition, the dependence of a conditional hyperposterior on the task data distribution is parameterized by a prior predictor using Local Coordinate Coding (LCC) (Yu et al., 2009) . In particular, if the classifier in each task is specialized to a parametric model, including deep neural network, the proposed LCCbased prior predictor predicts the model parameters using the sample set by exploiting the local information on the latent manifold. LCC-based prior predictor is invariant under permutations of its inputs and could be further used for unseen tasks. The main contributions of this work include: (i) We present a localized meta-learning framework which provides a means to tighten the original PAC-Bayes meta-learning bound (Pentina & Lampert, 2014; Amit & Meir, 2018) by minimizing the task-complexity term by choosing data-dependent prior; (ii) We propose an LCC-based prior predictor, an implementation of conditional hyperposterior, to generate local meta-knowledge for specific task; (iii) We derive a practical localized metalearning algorithm for deep neural networks by minimizing the bound; (iv) Experimental results demonstrate improved performance over meta-learning method in this field. 2 PRELIMINARIES 2.1 LOCAL COORDINATE CODING We first review some definitions of Local Coordinate Coding (LCC) (Yu et al., 2009) based on which we develop the proposed LCC-based prior predictor. Definition 1. (Lipschitz Smoothness (Yu et al., 2009).
Definition 2. (Coordinate Coding (Yu et al., 2009).) A coordinate coding is a pair (γ, C), where C ⊂ R d is a set of anchor points, and γ is a map of x ∈ R d to [γ u (x)] u∈C ∈ R |C| such that u γ u (x) = 1. It induces the following physical approximation of x in R d : γ(x) = u∈C γ u (x)u.

1. INTRODUCTION:

Recent years have seen a resurgence of interest in the field of meta-learning, or learning-to-learn (Thrun & Pratt, 2012) , especially for empowering deep neural networks the capability of fast adapting to unseen tasks just as humans (Finn et al., 2017; Ravi & Larochelle, 2017) . More concretely, the neural networks are trained from a sequence of datasets, associated with different learning tasks sampled from a meta-distribution (also called task environment (Baxter, 2000; Maurer, 2005) ). The principal aim of meta learner is to extract transferable meta-knowledge from observed tasks and facilitate the learning of new tasks sampled from the same meta-distribution. The performance is measured by the generalization ability from a finite set of observed tasks, which is evaluated by learning related unseen tasks. For this reason, there has been considerable interest in theoretical bounds on the generalization in terms of the meta-learning algorithm (Denevi et al., 2018b; a) .

One typical line of work (Pentina & Lampert, 2014; Amit & Meir, 2018) use PAC-Bayes bound to analyze the generalization behavior of the meta learner and quantify the relation between the expected loss on new tasks and the average loss on the observed tasks. In this setup, we formulate meta-learning as hierarchical Bayes. Accordingly, meta-knowledge is instantiated as a global distribution over all possible priors, which we call hyperprior and is chosen before observing training tasks. Each prior is a distribution over a family of classifiers w.r.t. a particular task. To learn versatile meta-knowledge across tasks, the meta learner observes a sequence of training tasks and adjusts its hyperprior into a hyperposterior distribution over the set of priors. To solve a new task, the base learner produces a posterior distribution over a family of classifiers based on the associated sample set and the prior generated by the hyperposterior.

However, such meta-knowledge is shared across tasks. The global hyperposterior is rather generic, typically not well-tailored to various specific tasks. Consequently, it leads to sub-optimal performance for any individual prediction task. As a motivational example, suppose we have two different tasks: distinguishing motorcycle versus bicycle and distinguishing motorcycle versus car.

Intuitively, each task uses distinct discriminative patterns and thus the desired meta-knowledge is required to extract these patterns simultaneously. This could be a challenging problem to represent it with a global hyperposterior since the most significant patterns in the first task could be irrelevant or even detrimental to the second task.

Hence, we are motivated to pursue a meta-learning framework to effectively define the hyperposterior. The inspiration comes from the PAC-Bayes literature on data distribution dependent priors (Catoni, 2007; Parrado-Hernández et al., 2012; Dziugaite & Roy, 2018) . The choice of posterior in each task is constrained by the need to minimize the relative entropy between prior and posterior since this divergence forms part of the bound and is typically large in standard PAC-Bayes Definition 3. (Latent Manifold (Yu et al., 2009) .) A subset M ⊂ R d is called a smooth manifold with an intrinsic dimension d := d M if there exists a constant c M such that given any x ∈ M, there exists d bases u 1 (x), . . . , u d (x) ∈ R d so that ∀x ∈ M:

inf γ∈R |C| x -x - d j=1 γ j u j (x) 2 ≤ c M x -x 2 2 ,

where γ = [γ 1 , . . . , γ d ] are the local codings w.r.t. the bases.

Definition 4. (Covering Number (Yu et al., 2009) .) The covering number N ( , M) is the smallest cardinality of an -ccover C ⊂ M. That is,

sup x∈M inf v∈C x -v ≤ .

Definition 2 and 3 imply that any point in R d can be expressed as a linear combination of a set of anchor points. Later, we will use them to develop the prior predictor.

2.2. PAC-BAYES META-LEARNING:

In order to present the advances proposed in this paper, we next recall some definitions in PAC-Bayes theory for single-task learning and meta-learning (Catoni, 2007; Baxter, 2000; Pentina & Lampert, 2014; Amit & Meir, 2018) . In the context of classification, we assume all tasks share the same input space X , output space Y, space of classifiers (hypotheses) H ⊂ {h : X → Y} and loss function

: Y × Y → [0, 1].

The meta learner observes n tasks in the form of sample sets S 1 , . . . , S n .

The number of samples in task i is denoted by m i . Each observed task i consists of a set of i.i.d.

samples S i = {(x j , y j )} mi j=1 , which is drawn from a data distribution S i ∼ D mi i . Following the meta-learning setup in (Baxter, 2000) , we assume that each data distribution D i is generated i.i.d.

from the same meta distribution τ . Let h(x) be the prediction of x, the goal of each task is to find a classifier h that minimizes the expected loss E x∼D (h(x), y). Since the underlying 'true' data distribution D i is unknown, the base learner receives a finite set of samples S i and produces an "optimal" classifier h = A b (S i ) with a deterministic learning algorithm A b (•) that will be used to predict the labels of unseen inputs.

PAC-Bayes theory studies the properties of randomized classifier, called Gibbs classifier. Let Q be a posterior distribution over H, to make a prediction, the Gibbs classifier samples a classifier h ∈ H according to Q and then predicts a label with the chosen h. The expected error under data distribution D and empirical error on the sample set S are then given by averaging over distribution Q, namely

er(Q) = E h∼Q E (x,y)∼D (h(x), y) and er(Q) = E h∼Q 1 m m j=1 (h(x j

), y j ), respectively. Then, we can get the following PAC-Bayes generalization bound of Catoni (2007) in a simplified form suggested by Germain et al. (2009) .

Theorem 1. (Catoni's bound) Let P be some prior distribution over H. Then for any δ ∈ (0, 1], and any real number c > 0, the following inequality holds uniformly for all posteriors distribution Q with probability at least 1 -δ,

EQUATION

The PAC-Bayes bound holds uniformly for all Q, it also holds for the data dependent Q. By choosing the posterior Q that minimizes the PAC-Bayes bound, we obtain an learning algorithm with generalization guarantees. Note that the value c allows to control the trade-off between the empirical error and the complexity term.

The goal of the meta learner is to extract meta-knowledge contained in the observed tasks that will be used as prior knowledge for learning new tasks. The prior knowledge P is in the form of a distribution over classifiers H. In each task, the base learner produces a posterior Q = A b (S, P ) over H based on a sample set S and a prior P . All tasks are learned through the same learning procedure. The meta learner treats the prior P itself as a random variable and assumes the metaknowledge is in the form of a distribution over all possible priors. Let hyperprior P be an initial distribution over priors, meta learner uses the observed tasks to adjust its original hyperprior P into hyperposterior Q from the learning process. The quality of the hyperposterior Q is measured by the expected task error of learning new tasks using priors generated from it, which is formulated as:

EQUATION

Accordingly, the empirical counterpart of the above quantity is given by:

êr(Q) = E P ∼Q 1 n n i=1 êr(Q = A b (S i , P )).

(3) , 1999) . Here we present a new meta-learning generalization bound with Gaussian randomization by using Catoni's bound in Eq. (1). In particular, the classifier h is parameterized as h w with w ∈ R dw . The prior and posterior is a distribution over the set of all possible parameters w. We choose both the prior P and posterior Q to be spherical Gaussians, i.e. P = N (w P , σ 2 w I dw )

and

Q = N (w Q , σ 2 w I dw ).

The mean w P is a random variable distributed first according to the hyperprior P, which we formulate as N (0, σ 2 w I dw ), and later according to hyperposterior Q, which we model as N (w Q , σ 2 w I dw ). When encountering a new task i, we first sample the mean of prior w P i from the hyperposterior N (w Q , σ 2 w I dw ), and then use it as a basis to learn the mean of posterior w Q i = A b (S i , P ), as shown in Figure 1 (left). Then, we could derive the following PAC-Bayes meta-learning bound.

Theorem 2. Consider the Meta-Learning (ML) framework, given the hyperprior P = N (0, σ 2 v I dv ), then for any hyperposterior Q, any c 1 , c 2 > 0 and any δ ∈ (0, 1] with probability ≥ 1 -δ we have,

EQUATION

where

c 1 = c1 1-e -c 1 and c 2 = c2 1-e -c 2 .

Proof. See Appendix B.3 for the proof.

Notice that the expected task generalization error is bounded by the empirical multi-task error plus two complexity terms. The first term demonstrates the environment-complexity which converges to zero if an infinite number of tasks are observed from the task environment (n → ∞), while the second is the task-complexity of the observed tasks which converges to zero when the sufficient samples in each task is observed (m i → ∞). Besides, the derived bound converges at the rate (Pentina & Lampert, 2014; Amit & Meir, 2018) , due to the use of Catoni's bound.

of O( 1 m ) instead of O( 1 √ m ) in

4. PAC-BAYES LOCALIZED META-LEARNING:

4.1 OVERALL FRAMEWORK Our motivation stems from a core challenge in PAC-Bayes meta-learning bound in 41, wherein the complexity term

n i=1 c 1 c 2 2c2nmiσ 2 w Ew Q i -w Q 2 is

typically vital to the bound and so finding the tightest possible bound generally depends on minimizing this term. It is obvious that the optimal

EQUATION

w . However, if the learned posteriors for each task are mutually exclusive, i.e., one learned posterior has a negative effect on another task, this term could be inevitably large.

w Q is the mean of hyperposterior Q and this term naturally indicates the divergence between the mean of prior w P i sampled from the hyperposterior Q and the mean of posterior w Q i in each task.

Therefore, we propose to adaptively choose the mean of prior w P i according to task i. It is obvious that the complexity term vanishes if we set w P i = w Q i , but the prior P i in each task has to be chosen independently of the sample set S i . Fortunately, the PAC-Bayes theorem allows us to choose prior upon the data distribution D i . Therefore, we propose a prior predictor Φ : D m → w P which receives task data distribution D m and outputs the mean of prior w P . In this way, the generated priors could focus locally on those regions of model parameters that are of particular interest in solving specific tasks.

Particularly, the prior predictor is parameterized as Φ v with v ∈ R dv . We abuse notation P and Q and assume v as a random variable distributed first according to the hyperprior P, which we reformulate as N (0, σ 2 v I dv ), and later according to hyperposterior Q, which we reformulate as

N (v Q , σ 2 v I dv ). Given a new task i, we first sample v from hyperposterior N (v Q , σ 2 v I dv ) and

estimate the mean of prior w P i by leveraging prior predictor

w P i = Φ v (D m i ).

Then, the base learner utilizes the sample set S i and the prior P i = N (w P i , σ 2 w I dw ) to produce a mean posterior

w Q i = A b (S i , P i ), as illustrated in Figure 1(right).

4.2. LCC-BASED PRIOR PREDICTOR:

To make w P close to w Q in each task, the prior predictor is required to (i) uncover the tight relation- 

= N (w Q , σ 2 w I dw ).

In the localized meta-learning, w P is produced by a prior predictor Φ v (D m ).

same category tend to be spatially clustered together while maintaining the separation between different classes. Take linear classifiers as an example, let w k be the parameters w.r.t. category k, the separability between classes is implemented as x • w k , which also explicitly encourages intra-class compactness. A reasonable choice of w k is to maximize the inner product distance with the input features in the same category and minimize the distance with the input features of the non-belonging categories. Besides, the prior predictor should be (ii) category-agnostic since it will be used continuously as new tasks and hence new categories become available. Lastly, it should be (iii) invariant under permutations of its inputs.

To satisfy the above conditions, we follow the idea of nearest class mean classifier (Mensink et al., 2013) , which represents class parameter by averaging its feature embeddings. This idea has been explored in transductive few-shot learning problem (Bertinetto et al., 2016; Yang et al., 2018) . Snell et al. ( 2017) learns a metric space across tasks such that when represented in this embedding, prototype (centroid) of each class can be used for label prediction in the new task. Qiao et al. (2018) directly predicts the classifier weights using the activations by exploiting the close relationship between the parameters and the activations in a neural network associated with the same category. In summary, the classification problem of each task is transformed as a generic metric learning problem which is shared across tasks. Once this mapping has been learned on observed tasks, due to the structure-preserving property, it could be easily generalized to new tasks. Formally, let each task be a K-class classification problem. Then the parameter of the classifier in task i is represented as

w i = [w i [1], . . . , w i [k], . . . , w i [K]].

The prior predictor for class k could be defined as:

EQUATION

where φ v (•) : R d → R dw is the feature embedding function, m ik is the number of samples belonging to category k, S ik and D ik are the sample set and data distribution for category k in task i. We call this function the expected prior predictor. Since data distribution D ik is considered unknown and our only insight as to D ik is through the sample set S ik , we approximate the expected prior predictor by its empirical counterpart, based on m ik observed samples in the category k:

EQUATION

which we call the empirical prior predictor. Although we can implement the embedding function φ v (•) with a multilayer perceptron (MLP), both input x and model parameter w are highdimensional, making the empirical prior predictor Φv (•) difficult to learn. According to Definition

(3), any points on the latent manifold can be approximated by a linear combination of a set of anchor points. Inspired by this, if the anchor points are sufficiently localized, the empirical prior predictor Φv (S) can also be approximated by a linear function w.r.t. a set of codings. Accordingly, we propose an LCC-based prior predictor, which is defined as:

EQUATION

where Φ v (u) ∈ R dw is the feature embedding of base u ∈ R d . As such, the parameters of LCC-based prior predictor w.r.t. category k can be represented as

v k = [Φ v k (u 1 ), Φ v k (u 2 ), . . . , Φ v k (u |C| )]

. Lemma 1 illustrates the approximation error. 6) and Eq. ( 7), let (γ, C) be an arbitrary coordinate coding on R d and φ be an (α, β)-Lipschitz smooth function. We have for all

EQUATION

where xj = u∈C γ u (x j )u. Then given any > 0, there exists a coding (γ, C) such that

EQUATION

)

Proof. See appendix B.1 for the proof.

The first inequality of Lemma 1 demonstrates that a good LCC-based prior predictor should make x close to its physical approximation x and should be localized. The second and third inequality show that if a set of anchor points C has cardinality O(d M N ( , M)), emprical prior predictor can be linearly approximated using LCC up to accuracy O(

√ d M 2

). The complexity of the LCC coding scheme depends only on the number of anchor points |C| instead of the input dimension. In fact, a small |C| is usually sufficient to achieve good approximation.

Optimization of LCC. We minimize the first inequality in (8) to obtain a set of anchor points. As with (Yu et al., 2009) , we simplify the localization error term by assuming x = x, and then we optimize the following objective function:

EQUATION

where x = u∈C γ u (x)u. In practice, we update C and γ by alternately optimizing a LASSO problem and a least-square regression problem, respectively.

4.3. PAC-BAYES LOCALIZED META-LEARNING BOUND WITH GAUSSIAN RANDOMIZATION:

In order to derive a PAC-Bayes generalization bound for localized meta-learning, we first bound the approximation error between expected prior predictor and LCC-based prior predictor.

Lemma 2. Given the definition of w P and wP in Eq. ( 5) and ( 7), let X be a compact set with radius R, i.e., ∀x, x ∈ X , xx ≤ R. For any δ ∈ (0, 1] with probability ≥ 1 -δ, we have

EQUATION

)

Proof. See appendix B.2 for the proof.

Lemma 2 shows that the approximation error between expected prior predictor and LCC-based prior predictor depends on (i) the concentration of prior predictor and (ii) the quality of LCC coding scheme. The first term implies the number of samples for each category should be larger for better approximation. This is consistent with the results of estimating the center of mass (Cristianini & Shawe-Taylor, 2004) . Based on Lemma 2, we have the following PAC-Bayes LML bound.

Theorem 3. Consider the Localized Meta-Learning (LML) framework, give the hyperprior P = N (0, σ 2 v I dv ), then for any hyperposterior Q, any c 1 , c 2 > 0 and any δ ∈ (0, 1] with probability ≥ 1 -δ we have,

EQUATION

where

c 1 = c1 1-e -c 1 and c 2 = c2 1-e -c 2 .

To get a better understanding, we further simplify the notation and obtain that

EQUATION

Proof. See appendix B.3 for the proof.

Similarly with the PAC-Bayes meta-learning bound in Theorem 2 and the bounds in (Pentina & Lampert, 2014; Amit & Meir, 2018) , the expected task error er(Q) is bounded by the empirical task error êr(Q) plus the task-complexity and environment-complexity terms. The main innovation

here is to exploit the potential to choose the mean of prior w P based on task data S. Intuitively, if the selection of the LCC-based prior predictor is appropriate, it will narrow the divergence between the mean of prior w P i sampled from the hyperposterior Q and the mean of posterior w Q i in each task. Therefore, the bound can be tighter than the ones in the meta-learning framework. Our empirical study in Section 5 illustrates that the algorithms derived from this bound can achieve better performance than the methods derived from standard PAC-Bayes meta-learning bounds.

When one is choosing the LCC-based prior predictor Φv (•), the number of anchor points |C|, there is a balance between accuracy and simplicity. As we increase |C|, it will essentially increase the expressive power of Φv (•) and reduce the complexity term

E v w Q -Φv Q (S) 2

. However, at the same time, it will increase the complexity term v Q 2 and make the bound loose. If we set |C| to 1, it is degraded to the regular meta-learning framework.

4.4. LOCALIZED META-LEARNING ALGORITHM:

Since the bound in (27) holds uniformly w.r.t. Q, the guarantees of Theorem 3 also hold for the resulting learned hyperposterior

Q = N (v Q , σ 2 v I dv )

, so the mean of prior w P sampled from the learned hyperposterior work well for future tasks. The PAC-Bayes localized meta-learning bound in (27) can be compactly written as

EQUATION

)

where α 1 , α 2 > 0 are hyperparameters. For task i, the learning algorithm A b (•) can be formulated as w i = arg min

w Q i E v êr i (Q i = N (w Q i , σ 2 w I dw ))

. Following Amit & Meir (2018) , we jointly opti-mize the parameters of LCC-based prior predictor v and the parameters of classifiers in each task w 1 , w 2 , . . . , w n , which is formulated as arg min v,w1,...,wn

EQUATION

)

We can optimize v and w via mini-batch SGD. The details of algorithms for meta-training are

given in Algorithms 1. The expectation over Gaussian distribution and its gradient can be efficiently 

E v êr i (w i ) + α 1 v Q 2 + n i=1 α2 mi E v w Q i - Φv Q (S i ) 2 .

Evaluate the gradient of J w.r.t. {v, w 1 , . . . , w n } using backpropagation. Take an optimization step. end while estimated by using the re-parameterization trick (Kingma & Welling, 2014; Rezende et al., 2014) .

For example, to sample w from the posterior

Q = N (w Q , σ 2 w I dw ), we first draw ξ ∼ N (0, I dw )

and then apply the deterministic function w Q + ξ σ, where is an element-wise multiplication. between the mean generated prior w P and the mean of learned posterior w Q .

5. EXPERIMENTS:



5.1. DATASETS AND SETUP:

We use CIFAR-100 and Caltech-256 in our experiments. CIFAR-100 (Krizhevsky, 2009) contains 60,000 images from 100 fine-grained categories and 20 coarse-level categories. As in (Zhou et al., 2018) , we use 64, 16, and 20 classes for meta-training, meta-validation, and meta-testing, respectively. Caltech-256 has 30,607 color images from 256 classes (Griffin et al., 2007) . Similarly, we split the dataset into 150, 56 and 50 classes for meta-training, meta-validation, and meta-testing. We consider 5-way classification problem. Each task is generated by randomly sampling 5 categories and each category contains 50 samples. The base model uses the convolutional architecture in (Finn et al., 2017) , which consists of 4 convolutional layers, each with 32 filters and a fully-connected layer mapping to the number of classes on top. High dimensional data often lies on some low dimensional manifolds. We utilize an auto-encoder to extract the semantic information of image data and then construct the LCC scheme based on the embeddings. The parameters of prior predictor and base model are random perturbations in the form of Gaussian distribution. We design two different meta-learning environment setting to validate the efficacy of the proposed method. The first one uses the pre-trained base model as an initialization, which utilizes all the meta-training classes (64-class classification in CIFAR-100 case) to train the feature extractor. The second one uses the random initialization. We compare the proposed LML method with ML-PL method (Pentina & Lampert, 2014) , ML-AM method (Amit & Meir, 2018) and ML-A which is derived from Theorem 2. In these methods, we use their main theorems about the PAC-Bayes generalization bound to derive the objective for the algorithm. We also compare with two typical meta-learning few-shot learning methods:

MAML (Finn et al., 2017) and MatchingNet (Vinyals et al., 2016) . To ensure a fair comparison, all approaches adopt the same network architecture and pre-trained feature extractor.

5.2. RESULTS:

In Figure 3 ing problem. The meta-training process requires millions of tasks and each task contains limited samples, which is not the case in our experiment. Scarce tasks in meta-training leads to severely meta-overfitting. In our method, the learned prior serves both as an initialization of base model and as a regularizer which restricts the solution space while allowing variation based on specific task data. It yields a model with smaller error than its unbiased counterpart when applied to a similar task.

Finally, we observe that if the pre-trained feature extractor is provided, all of these methods do better than meta-training with random initialization. This is because pre-trained feature extractor can be regarded as a data-dependent hyperpior. It is closer to the hyperposteior than the randomly initialized hyperprior. Therefore, it reduces the environment complexity term and improves the generalization performance.

In Figure 4 (b), we show the divergence between the mean of generated prior w P from meta model and the mean of learned posterior w Q for LML and ML-A. This further validates the effectiveness of the LCC-based prior predictor which could narrow the divergence term and thus tight the bound.

In Figure 4 (a), we vary the number of bases |C| in LCC scheme from 4 to 256, the optimal value is around 64 in both datasets. This indicates that LML is sensitive to the number of bases |C|, which further affects the quality of LCC-based prior predictor and the performance of LML.

6. RELATED WORK:

Meta-Learning. Meta-learning literature commonly considers the empirical task error by directly optimizing a loss of meta learner across tasks in the training data. Recently, this has been success-fully applied in a variety of models for few-shot learning (Ravi & Larochelle, 2017; Snell et al., 2017; Finn et al., 2017; Vinyals et al., 2016) 2019) consider task adaptation when using meta-knowledge for specific tasks, all of them are not based on generalization error bounds, which is the focus of our work. Meta-learning in the online setting has regained attention recently (Denevi et al., 2018b; a; 2019; Balcan et al., 2019) , in which online-to-batch conversion results could imply generalization bounds. Galanti et al. (2016) analyzes transfer learning in neural networks with PAC-Bayes tools.

Most related to our work are (Pentina & Lampert, 2014; Amit & Meir, 2018) which provide a PAC-Bayes generalization bound for meta-learning framework. In contrast, neither work considers localized meta-knowledge for specific tasks.

Localized PAC-Bayes Learning. There has been a prosperous line of research for learning priors to improve the PAC-Bayes bounds Catoni (2007) ; Guedj (2019) . (Parrado-Hernández et al., 2012) showed that priors can be learned by splitting the available training data into two parts, one for learning the prior, one for learning the posterior. (Lever et al., 2013) derived an expression for the overall best prior, i.e. the distribution resulting in the smallest possible bound value and bounded the KL divergence by a term independent of data distribution. Recently, (Rivasplata et al., 2018) bounded the KL divergence by investigating the stability of the hypothesis. (Dziugaite & Roy, 2018) optimized the prior term in a differentially private way. In summary, theses methods construct some quantities that reflect the underlying data distribution, rather than the sample set, and then choose the prior P based on these quantities. These works, however, are only applicable for single-task problem and could not transfer knowledge across tasks in meta-learning setting.

7. CONCLUSION:

This work contributes a novel localized meta-learning framework from a theoretical perspective. We 

A NOTATIONS:

Let φ v (•) : R d → R dw be the feature embedding function. m ik denotes the number of samples belonging to category k. S ik and D ik are the sample set and data distribution for category k in task i, respectively. Then, the expected prior predictor w.r.t. class k in task i is defined as:

w P i [k] = Φ v (D m ik ik ) = E S ik ∼D m ik ik 1 m ik xj ∈S ik φ v (x j ).

The empirical prior predictor w.r.t. class k in task i is defined as:

ŵP i [k] = Φv (S ik ) = 1 m ik xj ∈S ik φ v (x j ).

The LCC-based prior predictor w.r.t. class k in task i is defined as:

wP i [k] = Φv (S ik ) = 1 m ik xj ∈S ik u∈C γ u (x j )Φ v (u).

B THEORETICAL RESULTS:



B.1 PROOF OF LEMMA 1:

This lemma bounds the error between the empirical prior predictor ŵP i [k] and the LCC-based prior

predictor wP i [k].

Lemma 1 Given the definition of ŵP i [k] and wP i [k] in Eq. ( 6) and Eq. ( 7), let (γ, C) be an arbitrary coordinate coding on R dx and φ be an (α, β)-Lipschitz smooth function and . We have for all

EQUATION

where xj = u∈C γ u (x j )u. Then given any > 0, there exists a coding (γ, C) such that

EQUATION

)

Proof. Let xj = u∈C γ u (x j )u. We have

Φv (S ik ) -Φv (S ik ) 2 = 1 m ik xj ∈S ik Φ v (x j ) - u∈C γ u (x j )Φ v (u) 2 ≤ 1 m ik xj ∈S ik Φ v (x j ) -Φ v (x j ) 2 + u∈C γ u (x j )(Φ v (u) -Φ v (x j ) 2 = 1 m ik xj ∈S ik Φ v (x j ) -Φ v (x j ) 2 + u∈C γ u (x j )(Φ v (u) -Φ v ( u∈C γ u (x j )u)) -∇Φ v (x j )(u -xj ) 2 ≤ 1 m ik xj ∈S ik Φ v (x j ) -Φ v (x j ) 2 + u∈C |γ u (x j )| (Φ v (u) -Φ v ( u∈C γ u (x j )u)) -∇Φ v (x j )(u -xj ) 2 ≤ 1 m ik xj ∈S ik α x j -xj 2 + β u∈C xj -u 2 2 = O α,β (γ, C)

In the above derivation, the first inequality holds by the triangle inequality. The second equality holds since u∈C γ u (x j ) = 1 for all x j . The last inequality uses the assumption of (α, β)-Lipschitz

smoothness of Φ v (•).

According to the Manifold Coding Theorem in (Yu et al., 2009) , if the data points x lie on a compact smooth manifold M. Then given any > 0, there exists anchor points C ⊂ M and coding γ such that

EQUATION

This implies the desired bound.

The first inequality of this lemma demonstrates that the quality of LCC approximation is bounded by two terms: the first term x j -xj 2 indicates x should be close to its physical approximation

x, the second term xju implies that the coding should be localized. The second and third inequality show that the approximation error of local coordinate coding depends on the intrinsic dimension of the manifold instead of the dimension of input. If a set of anchor points C has cardinality O(d M N ( , M)), emprical prior predictor can be linearly approximated using LCC up to accuracy

O( √ d M 2 ).

B.2 PROOF OF LEMMA 2:

In order to proof Lemma 2, we first introduce a relevant theorem.

Theorem 4. (Vector-valued extension of McDiarmid's inequality (Rivasplata et al., 2018) ) Let X 1 , . . . , X m ∈ X be independent random variables, and f : X m → R dw be a vector-valued mapping function. If, for all i ∈ {1, . . . , m}, and for all x 1 , . . . , x m , x i ∈ X , the function f satisfies

EQUATION

The above theorem indicates that bounded differences in norm implies the concentration of f (X 1:m ) around its mean in norm, i.e., f (X 1:m ) -E[f (X 1:m )] is small with high probability.

Under review as a conference paper at ICLR 2020 Then, we bound the error between expected prior predictor w P i and the empirical prior predictor ŵP i .

Lemma 3. Given the definition of w P i [k] and ŵP i [k] in ( 5) and ( 6), let X be a compact set with radius R, i.e., ∀x, x ∈ X , xx ≤ R. For any δ ∈ (0, 1] with probability ≥ 1 -δ, we have

EQUATION

Proof. According to the definition of Φv (•) in ( 6), for all points x 1 , . . . , x j-1 , x j+1 , . . . , x m k , x j in the sample set S ik , we have

EQUATION

where R denotes the domain of x, say R = sup x x . The first inequality follows from the Lipschitz smoothness condition of Φ v (•) and the second inequality follows by the definition of domain X . Utilizing Theorem 4, for any δ ∈ (0, 1] with probability ≥ 1 -δ we have

EQUATION

This implies the bound.

Lemma 3 shows that the bounded difference of function Φ v (•) implies its concentration, which can be further used to bound the differences between empirical prior predictor wP i [k] and expected prior predictor

w P i [k]

. Now, we bound the error between expected prior predictor w P i and the LCC-based prior predictor wP i .

Lemma 2 Given the definition of w P i and wP i in ( 5) and ( 7), let X be a compact set with radius R, i.e., ∀x, x ∈ X , xx ≤ R. For any δ ∈ (0, 1] with probability ≥ 1 -δ, we have

EQUATION

)

Proof According to the definition of w P , wP and ŵP , we have

EQUATION

Substitute Lemma 3 and Lemma 1 into the above inequality, we can derive

EQUATION

)

This gives the assertion.

Lemma 2 shows that the approximation error between expected prior predictor and LCC-based prior predictor depends on the number of samples in each category and the quality of the LCC coding scheme.

B.3 PROOF OF THEOREM 3:

Theorem 3 Let Q be the posterior of base learner Q = N (w Q , σ 2 w I dw ) and P be the prior N ( Φv (S), σ 2 w I dw ). The mean of prior is produced by the LCC-based prior predictor Φv (S) in Eq. ( 7) and its parameter v is sampled from the hyperposterior of meta learner Q = N (v Q , σ 2 v I dv ). Give the hyperprior P = N (0, σ 2 v I dv ), then for any hyperposterior Q, any c 1 , c 2 > 0 and any δ ∈ (0, 1] with probability ≥ 1 -δ we have,

EQUATION

where c 1 = c1 1-e -c 1 and c 2 = c2 1-e -c 2 . We can simplify the notation and obtain that

EQUATION

)

Proof Our proof contains two steps. First, we bound the error within observed tasks due to observing a limited number of samples. Then we bound the error on the task environment level due to observing a finite number of tasks. Both of the two steps utilize Catoni's classical PAC-Bayes bound (Catoni, 2007) to measure the error. We give here a general statement of the Catoni's classical PAC-Bayes bound.

Theorem 5. (Classical PAC-Bayes bound, general notations) Let X be a sample space and X be some distribution over X , and let F be a hypotheses space of functions over X . Define a loss function g(f, X) : F × X → [0, 1], and let X G 1 {X 1 , . . . , X G } be a sequence of K independent random variables distributed according to X. Let π be some prior distribution over F (which must not depend on the samples X 1 , . . . , X k ). For any δ ∈ (0, 1], the following bounds holds uniformly for all posterior distribution ρ over F (even sample dependent),

EQUATION

)

First step We utilize Theorem 5 to bound the generalization error in each of the observed tasks.

Let i ∈ 1, . . . , n be the index of task. For task i, we substitute the following definition into the Catoni's PAC-Bayes Bound. Specifically, X g (x ij , y ij ), K m i denote the samples and X D i denotes the data distribution. We instantiate the hypotheses with a hierarchical model f (v, w), where v ∈ R dv and w ∈ R dw are the parameters of meta learner (prior predictor) Φ v (•) and base learner h(•) respectively. The loss function only considers the base learner, which is defined as g(f, X) (h w (x), y). The prior over model parameter is represented as π (P, P ) (N (0, σ 2 v I dv ), N (w P , σ 2 w I dw )), a Gaussian distribution (hyperprior of meta learner) centered at 0 and a Gaussian distribution (prior of base learner) centered at w P , respectively. We set the posterior to ρ Then we sample base learner parameter w from posterior N (w Q , σ 2 w I dw ) and compute the incurred loss (h w (x), y). On the whole, meta-learning algorithm A m (S 1 , . . . , S n , P) observes a series of tasks S 1 , . . . , S n and adjusts its hyperprior P = N (v P , σ 2 v I dv ) into hyperposterior

(Q, Q) (N (v Q , σ 2 v I dv ), N (w Q , σ 2 w I dw )),

Q = A m (S 1 , . . . , S n , P) = N (v Q , σ 2 v I dv ).

The KL divergence term between prior π and posterior ρ is computed as follows:

EQUATION

)

In our localized meta-learning framework, in order to make KL(Q||P ) small, the center of prior distribution w P is generated by the expected prior predictor w P = Φ v (D). However, the data distribution D is considered unknown and our only insight as to D ik is through the sample set S ik . In this work, we approximate the expected prior predictor Φ v (D) with the LCC-based prior predictor wP = Φv (S). Denote the term

E v∼N (v Q ,σ 2 v I dv ) 1 2σ 2 w w Q -w P 2 by E v 1 2σ 2 w w Q -w P 2

for convenience, we have

EQUATION

)

Since wP i = Φv (S i ) = [ Φv (S i1 ), . . . , Φv (S ik ), . . . , Φv (S iK )], we have

EQUATION

where V v [ Φv (S ik ) ] denotes the variance of Φv (S ik ) . The last equality uses the fact that d v = |C|d w . Combining Lemma 2, for any δ ∈ (0, 1] with probability ≥ 1 -δ we have

EQUATION

Then, according to Theorem 5, we obtain that for any δi 2 > 0

EQUATION

for all observed tasks i = 1, . . . , n. Define δ = δi 2 and combine inequality (33), we obtain

EQUATION

Using the notations in Section 4, the above bound can be simplified as

EQUATION

Second step Next we bound the error due to observing a limited number of tasks from the environment. We reuse Theorem 5 with the following substitutions. The samples are (D i , m i , S i ), i = 1, . . . , n, where (D i , m i ) are sampled from the same meta distribution τ and S i ∼ D mi i . The hyposthesis is parameterized as Φ v (D) with meta learner parameter v. The loss function is g(f, X) E (h w (x), y)

EQUATION

)

Using the term in Section 4, the above bound can be simplified as

P (D m i i )∼τ,Si∼D m i i ,i=1,...,n er(Q) ≤ c 1 1 -e -c1 • 1 n n i=1 E v∼N (v Q ,σ 2

v I dv ),w P =Φv(D),Pi=N (w P ,σ 2 w I dw )

er(A b (S i , P i ))

EQUATION

Finally, by employing the union bound, we could bound the probability of the intersection of the events in ( 36) and ( 38 êr(A b (S i , P i ))

EQUATION

We can further simplify the notation and obtain that

EQUATION

where c 1 = c1 1-e -c 1 and c 2 = c2 1-e -c 2 . This completes the proof. Theorem 2 Let Q be the posterior of base learner Q = N (w Q , σ 2 w I dw ) and P be the prior N (w P , σ 2 w I dw ). The mean of prior is sampled from the hyperposterior of meta learner Q = N (w Q , σ 2 w I dw ). Give the hyperprior P = N (0, σ 2 w I dw ), then for any hyperposterior Q, any c 1 , c 2 > 0 and any δ ∈ (0, 1] with probability ≥ 1 -δ we have,

EQUATION

where c 1 = c1 1-e -c 1 and c 2 = c2 1-e -c 2 .

464:

Proof Instead of generating the mean of prior with a prior predictor, the vanilla meta-learning framework directly produces the mean of prior w P by sampling from hyperposterior Q = N (w Q , σ 2 w I dw ). Then the base learner algorithm A b (S, P ) utilizes the sample set S and the prior P = N (w P , σ 2 w I dw ) to produce a posterior Q = A b (S, P ) = N (w Q , σ 2 w I dw ). Similarly with the two-steps proof in Theorem 3, we first get an intra-task bound by using Theorem 5. For any δ i > 0, we have

EQUATION

The term E

w P i ∼N (w Q ,σ 2 w I dw ) 1 2σ 2 w w Q i -w P i

2 can be simplified as

EQUATION

where V (44) 

:



Figures and Tables:

Figure 3: The average test accuracy of learning a new task for different number of training tasks (|C| = 64).

Figure 4: (a) The impact of the number of bases |C| in LCC. (b) The divergence value (normalized) between the mean generated prior w P and the mean of learned posterior w Q .

, we demonstrate the average test error of learning a new task based on the number of training tasks in different settings (with or without a pre-trained feature extractor). It is obvious that the performance continually increases as we increase the number of training tasks for all the methods. This is consistent with the generalization bounds that the complexity term converges to zero if large numbers of tasks are observed. ML-A consistently outperforms ML-PL and ML-AM since the bound w.r.t. ML-A in Theorem 2 converges at the rate of O( 1 m ) while the bounds w.r.t. ML-PL and ML-AM converge at the rate of O( 1 √ m ). This demonstrates the importance of using tight generalization bound. Our proposed LML significantly outperforms the baselines, which validates the effectiveness of the proposed LCC-based prior predictor. It is a more suitable representation for meta-knowledge than the traditional global hyperposterior in ML-A, ML-AM, and ML-PL. Moreover, we can find that all PAC-Bayes baselines outperform MAML and MatchingNet. Note that MAML and MatchingNet adopt the episodic training paradigm to solve the few-shot learn-

propose a generalization bound based on PAC-Bayes theory with Gaussian randomization. Instead of formulating meta-knowledge as a global distribution, we propose an LCC-based prior predictor to output local meta-knowledge by using task information. We further develop a practical algorithm with deep neural network based on the bound. An interesting topic for future work would be to explore other principle to construct the prior predictor and apply the localized meta-learning framework to a more realistic scenario that tasks are sampled non-i.i.d. from an environment. Another challenging problem is to extend our techniques to derive localized meta-learning algorithms for regression and reinforcement learning problem. This supplementary document contains the technical proofs of theoretical results and details of experiments. It is structured as follows: Appendix A present notations for prior predictor. Appendix B gives the proofs of the main results. Appendix B.1 and B.2 show the approximation error between LCC-based prior predictor and empirical prior predictor, expected prior predictor, respectvely. They are used in the proof of Theorem 3. Next, in Appendix B.3 and B.4 we show the PAC-Bayes generalization bound of localized meta-learning in Theorem 3 and also provides the PAC-Bayes generalization bound of regular meta-learning in Theorem 2. Finally, details of experiments are presented in Appendix C.

a Gaussian distribution (hyperposterior of meta learner) centered at v Q and a Gaussian distribution (posterior of base learner) centered at w Q . According to Theorem 5, the generalization bound holds for any posterior distribution including the one generated in our localized meta-learning framework. Specifically, we first sample v from hyperposterior N (v Q , σ 2 v I dv ) and estimate w P by leveraging expected prior predictor w P = Φ v (D). The base learner algorithm A b (S, P ) utilizes the sample set S and the prior P = N (w P , σ 2 w I dw ) to produce a posterior Q = A b (S, P ) = N (w Q , σ 2 w I dw ).

Q ,σ 2 w I dw ) (h w (x), y), where w Q = A b (S i , P i ). Let π N (0, σ 2 v I dv ) bethe prior over meta learner parameter, the following holds for any δ 0 > 0,

) For any δ > 0, set δ Q ,σ 2 v I dv ),w P =Φv(D),Pi=N (w P ,σ 2 w I dw )

the variance of w P i . Then we get an inter-task bound. For anyδ 0 > 0, ∼N (w Q ,σ 2 w I dw ) E w∼N (w Q ,σ 2 w I dw ) E (x,y)∼Di (h w (x), y) + 1 (1 -e -c1 )n 1 2σ 2 w w Q 2 + log 1 δ 0 , ∀Q ≥ 1 -δ 0 .

ship between the sample set and model parameter. Intuitively, features and parameters yield similar local and global structures in their respective spaces in the classification problem. Features in the

Table content: <table><tr><td>Task 1</td><td>Task 2</td><td>Task n</td><td>Future Task•</td><td>Task 1</td><td>Task 2</td><td>Task n</td><td>Future Task•</td></tr><tr><td>𝑺 𝟏 ~𝑫𝟏 𝒎 𝟏</td><td>𝑺 𝟐 ~𝑫𝟐 𝒎 𝟐</td><td>𝑺 𝒏 ~𝑫𝒏 𝒎 𝒏</td><td>𝑺~𝑫 𝒎</td><td>𝑺 𝟏 ~𝑫𝟏 𝒎 𝟏</td><td>𝑺 𝟐 ~𝑫𝟐 𝒎 𝟐</td><td>𝑺 𝒏 ~𝑫𝒏 𝒎 𝒏</td><td>𝑺~𝑫 𝒎</td></tr><tr><td colspan="2">Meta Learner (A global distribution 𝓠)</td><td>Prior</td><td>Base Learner</td><td colspan="2">Meta Learner (Prior Predictor 𝚽)</td><td>Prior</td><td>Base Learner</td></tr><tr><td colspan="2">𝒩(𝒘 𝓠 , 𝝈 𝒘 𝟐 𝑰 𝒅 𝒘 )</td><td>𝒘 𝑷</td><td>𝒘 𝑸</td><td/><td>𝚽 𝐯 (𝐃 𝐦 )</td><td>𝒘 𝑷</td><td>𝒘 𝑸</td></tr><tr><td colspan="8">Figure 1: Comparison between meta-learning (left) and localized meta-learning (right). In regular</td></tr><tr><td colspan="8">meta-learning, the mean of prior w P is sampled from a global hyperposterior distribution Q</td></tr></table>

Figure2: A geometric view of Local Coordinate Coding. Given a set of anchor points, if data lie on a manifold, the empirical prior predictor Φv (S) can be locally approximated by a linear function w.r.t. the coding. Given all bases, Φv (S) can be globally approximated.

Table content: <table><tr><td>Local linearity</td><td/></tr><tr><td>Φ(x)</td><td/></tr><tr><td>X</td><td>Manifold Anchor Point</td></tr></table>

Algorithm 1 Localized Meta-Learning (LML) algorithm Input: Data sets of observed tasks: S 1 , . . . , S n . Output: Learned prior predictor Φ parameterized by v. Initialize v ∈ R dv and w i ∈ R dw for i = 1 . . . , n. Construct LCC scheme (γ, C) from the whole training data by optimizing Eq. (10). while not converged do for each task i ∈ {1, . . . , n} do Sample a random mini-batch from the data S i ⊂ S i . Approximate E

Table content: <table><tr><td>end for Compute the objective in (15), i.e. J ←</td><td>n i=1</td></tr></table>

. AlthoughVuorio et al. (2018);Rusu et al. (2019);Zintgraf et al. (2019);Wang et al. (

Table content: <table/>

Peer review (iclr2020):
Post-rebuttal: =========== Thank you to the authors for responding to my review, and for adding the comparison to other meta-learning methods besides Amit et al. (2018), which makes it clearer in which settings this technique outperforms purely discriminative approaches (in particular with few tasks & many samples from each task). However, I would assume that not using support-query partitioning for MAML and Matching Nets is likely to reduce their performance. > *Second, from the algorithm perspective, we use the whole sample set S as the input for LCC-based prior predictor _x0008_ar{w}^P = _x0008_ar{Phi}_v(S) .* Thanks to the authors for this clarification--it is now clear to me that the experimental setup is not the episodic training setup of Vinyals et al. (2016) that partitions episodes into support and query sets, thus the difficulty of comparison to other few-shot learning methods that use this setup. However, this exposes a potential problem with the formulation: As the authors state in the submission, *...the prior P_i in each task has to be chosen independently of the sample set S_i*, in alignment with prior works in data-dependent PAC-Bayes bounds [Catoni, 2007; Parrado-Hernandez et al., 2012; Dziugaite & Roy, 2018]. However, even though the authors begin section 4.1 by stating *Fortunately, the PAC-Bayes theorem allows us to choose prior upon the data distribution D_i. Therefore, we propose a prior predictor...which receives task data distribution Dm and outputs the mean of prior wP*; the prior predictor employed is the *empirical prior predictor* that operates directly on the sample set S_i. This appears to be a contradiction that is not sufificiently addressed in the text (nor in the response to Reviewer #4). To fix this, the authors would have to more clearly explain why their theoretical results do not require the separation of task-specific data into a subset of data used to produce the prior and a subset used in the computation of the bound, or adapt the experimental setting to meet this theoretical requirement (in which case the setup is very similar to the support-query partitioning commonly used to evaluate few-shot learning methods, therefore bringing into question the necessity of using an alternate evaluation protocol to the one that is standard in few-shot learning). Before rebuttal: ============= The submission makes use of a data-dependent PAC-Bayes bound on the generalization error of a classifier estimated in a few-shot learning setup. The episodic few-shot learning setup from Vinyals et al. (2016) provides a small dataset for each task, partitioned into a support and a query set; at test time, only the labels for the support set are provided. The submission takes advantage of this setup by leveraging the support set in the construction of a data-dependent prior, an idea referred to as *locality*; this is in contrast to prior work in PAC-Bayes for hierarchical models (e.g., Pentina & Lampert, 2014; Amit & Meir, 2018) in which the data-dependency enters only across tasks, and not within a task. Strengths: - Coherent formulation of data-dependent PAC-Bayes for a meta-learning setting that partitions episodic data into a support set (used to compute the data-dependent prior) and a query set (used to produce the posterior. - The method outperforms prior approaches constructed from PAC-Bayes generalization bounds (LML; ML-A; ML-AM; ML-PL) on the Caltech-256 and CIFAR-100 datasets. Weaknesses: - The framing as *localized meta-learning* obscures the lack of difference from the standard partitioning in few-shot episodes in a support and query set. - The proposed method makes heavy use of prior machinery (LCC, prototype-based prior predictor), and as such, the algorithmic novelty is limited. - No comparison is made to approaches that are not constructed use PAC-Bayes generalization bounds (Vinyals et a. 2016; Finn et al. 2017), even though they are readily applied in such settings.