Year: 2019

Abstract:
Meta-learning methods learn the meta-knowledge among various training tasks 1 and aim to promote the learning of new tasks under the task similarity assumption. 2 However, such meta-knowledge is often represented as a fixed distribution, which 3 is too restrictive to capture various specific task information. In this work, we 4 present a localized meta-learning framework based on the PAC-Bayes theory. In 5 particular, we propose an LCC-based prior predictor that allows the meta learner to 6 adaptively generate local meta-knowledge for specific tasks. We further develop 7 a practical algorithm with deep neural network based on the bound. Empirical 8 results on real-world datasets demonstrate the efficacy of the proposed method. 9

Meta-learning methods learn the meta-knowledge among various training tasks1 and aim to promote the learning of new tasks under the task similarity assumption.2 However, such meta-knowledge is often represented as a fixed distribution, which3 is too restrictive to capture various specific task information. In this work, we4 present a localized meta-learning framework based on the PAC-Bayes theory. In5 particular, we propose an LCC-based prior predictor that allows the meta learner to6 adaptively generate local meta-knowledge for specific tasks. We further develop7 a practical algorithm with deep neural network based on the bound. Empirical8 results on real-world datasets demonstrate the efficacy of the proposed method.9
1 INTRODUCTION10
Recent years have seen a resurgence of interest in the field of meta-learning, or learning-to-learn11 (Thrun & Pratt, 2012), especially for empowering deep neural networks the capability of fast adapt-12 ing to unseen tasks just as humans (Finn et al., 2017; Ravi & Larochelle, 2017). More concretely,13 the neural networks are trained from a sequence of datasets, associated with different learning tasks14 sampled from a meta-distribution (also called task environment (Baxter, 2000; Maurer, 2005)). The15 principal aim of meta learner is to extract transferable meta-knowledge from observed tasks and16 facilitate the learning of new tasks sampled from the same meta-distribution. The performance is17 measured by the generalization ability from a finite set of observed tasks, which is evaluated by18 learning related unseen tasks. For this reason, there has been considerable interest in theoretical19 bounds on the generalization in terms of the meta-learning algorithm (Denevi et al., 2018b;a).20
One typical line of work (Pentina & Lampert, 2014; Amit & Meir, 2018) use PAC-Bayes bound to21 analyze the generalization behavior of the meta learner and quantify the relation between the ex-22 pected loss on new tasks and the average loss on the observed tasks. In this setup, we formulate23 meta-learning as hierarchical Bayes. Accordingly, meta-knowledge is instantiated as a global dis-24 tribution over all possible priors, which we call hyperprior and is chosen before observing training25 tasks. Each prior is a distribution over a family of classifiers w.r.t. a particular task. To learn versa-26 tile meta-knowledge across tasks, the meta learner observes a sequence of training tasks and adjusts27 its hyperprior into a hyperposterior distribution over the set of priors. To solve a new task, the base28 learner produces a posterior distribution over a family of classifiers based on the associated sample29 set and the prior generated by the hyperposterior.30
However, such meta-knowledge is shared across tasks. The global hyperposterior is rather generic,31 typically not well-tailored to various specific tasks. Consequently, it leads to sub-optimal perfor-32 mance for any individual prediction task. As a motivational example, suppose we have two dif-33 ferent tasks: distinguishing motorcycle versus bicycle and distinguishing motorcycle versus car.34 Intuitively, each task uses distinct discriminative patterns and thus the desired meta-knowledge is35 required to extract these patterns simultaneously. This could be a challenging problem to represent36 it with a global hyperposterior since the most significant patterns in the first task could be irrelevant37 or even detrimental to the second task.38
Hence, we are motivated to pursue a meta-learning framework to effectively define the hyperpos-39 terior. The inspiration comes from the PAC-Bayes literature on data distribution dependent priors40 (Catoni, 2007; Parrado-Hernández et al., 2012; Dziugaite & Roy, 2018). The choice of posterior41 in each task is constrained by the need to minimize the relative entropy between prior and pos-42 terior since this divergence forms part of the bound and is typically large in standard PAC-Bayes43
approaches (Lever et al., 2013). Thus, choosing an appropriate prior for each task which is close to44 the related posterior could yield improved generalization bounds.45
Inspired by this, we propose a Localized Meta-Learning (LML) framework. Instead of formulating46 meta-knowledge as a global hyperposterior, we learn a conditional hyperposterior given task data47 distribution that allows a meta learner to adaptively generate an appropriate prior for a new task.48 However, the task data distribution is unknown, and our only perception for it is via the associated49 sample set. Nevertheless, if the conditional hyperposterior is relatively stable to perturbations of the50 sample set, then the generated prior could still reflect the underlying task data distribution, resulting51 in a generalization bound that still holds with smaller probability. Following this intuition, the52 dependence of a conditional hyperposterior on the task data distribution is parameterized by a prior53 predictor using Local Coordinate Coding (LCC)(Yu et al., 2009). In particular, if the classifier in54 each task is specialized to a parametric model, including deep neural network, the proposed LCC-55 based prior predictor predicts the model parameters using the sample set by exploiting the local56 information on the latent manifold. LCC-based prior predictor is invariant under permutations of its57 inputs and could be further used for unseen tasks.58
The main contributions of this work include: (i) We present a localized meta-learning framework59 which provides a means to tighten the original PAC-Bayes meta-learning bound (Pentina & Lam-60 pert, 2014; Amit & Meir, 2018) by minimizing the task-complexity term by choosing data-dependent61 prior; (ii) We propose an LCC-based prior predictor, an implementation of conditional hyperposte-62 rior, to generate local meta-knowledge for specific task; (iii) We derive a practical localized meta-63 learning algorithm for deep neural networks by minimizing the bound; (iv) Experimental results64 demonstrate improved performance over meta-learning method in this field.65
2 PRELIMINARIES66
2.1 LOCAL COORDINATE CODING67
We first review some definitions of Local Coordinate Coding (LCC) (Yu et al., 2009) based on which68 we develop the proposed LCC-based prior predictor.69 Definition 1. (Lipschitz Smoothness (Yu et al., 2009).) A function f(x) on Rd is a (α, β)-Lipschitz70 smooth w.r.t. a norm ‖ ·‖ if ‖f(x)−f(x′)‖ ≤ α‖x−x′‖ and ‖f(x′)−f(x)−∇f(x)>(x′−x)‖ ≤71 β‖x− x′‖2.72 Definition 2. (Coordinate Coding (Yu et al., 2009).) A coordinate coding is a pair (γ, C), where73 C ⊂ Rd is a set of anchor points, and γ is a map of x ∈ Rd to [γu(x)]u∈C ∈ R|C| such74 that ∑ u γu(x) = 1. It induces the following physical approximation of x in Rd : γ(x) =75 ∑ u∈C γu(x)u.76
Definition 3. (Latent Manifold (Yu et al., 2009).) A subsetM ⊂ Rd is called a smooth manifold with an intrinsic dimension d := dM if there exists a constant cM such that given any x ∈ M, there exists d bases u1(x), . . . ,ud(x) ∈ Rd so that ∀x′ ∈M:
inf γ∈R|C| ‖x′ − x− d∑ j=1 γjuj(x)‖2 ≤ cM‖x′ − x‖22,
where γ = [γ1, . . . , γd]> are the local codings w.r.t. the bases.77 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 Rd can be expressed as a linear combination of a set of78 anchor points. Later, we will use them to develop the prior predictor.79
2.2 PAC-BAYES META-LEARNING80
In order to present the advances proposed in this paper, we next recall some definitions in PAC-Bayes81 theory for single-task learning and meta-learning (Catoni, 2007; Baxter, 2000; Pentina & Lampert,82
2014; Amit & Meir, 2018). In the context of classification, we assume all tasks share the same input83 space X , output space Y , space of classifiers (hypotheses) H ⊂ {h : X → Y} and loss function84 ` : Y × Y → [0, 1]. The meta learner observes n tasks in the form of sample sets S1, . . . , Sn.85 The number of samples in task i is denoted by mi. Each observed task i consists of a set of i.i.d.86 samples Si = {(xj , yj)}mij=1, which is drawn from a data distribution Si ∼ D mi i . Following the87 meta-learning setup in (Baxter, 2000), we assume that each data distribution Di is generated i.i.d.88 from the same meta distribution τ . Let h(x) be the prediction of x, the goal of each task is to find89 a classifier h that minimizes the expected loss Ex∼D`(h(x), y). Since the underlying ‘true’ data90 distribution Di is unknown, the base learner receives a finite set of samples Si and produces an91 “optimal” classifier h = Ab(Si) with a deterministic learning algorithm Ab(·) that will be used to92 predict the labels of unseen inputs.93
PAC-Bayes theory studies the properties of randomized classifier, called Gibbs classifier. Let Q be94 a posterior distribution overH, to make a prediction, the Gibbs classifier samples a classifier h ∈ H95 according toQ and then predicts a label with the chosen h. The expected error under data distribution96 D and empirical error on the sample set S are then given by averaging over distribution Q, namely97 er(Q) = Eh∼QE(x,y)∼D`(h(x), y) and êr(Q) = Eh∼Q 1m ∑m j=1 `(h(xj), yj), respectively. Then,98
we can get the following PAC-Bayes generalization bound of Catoni (2007) in a simplified form99 suggested by Germain et al. (2009).100
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− δ,
er(Q) ≤ c 1− e−c
[ êr(Q) +
KL(Q||P ) + log 1δ mc
] . (1)
The PAC-Bayes bound holds uniformly for allQ, it also holds for the data dependentQ. By choosing101 the posteriorQ that minimizes the PAC-Bayes bound, we obtain an learning algorithm with general-102 ization guarantees. Note that the value c allows to control the trade-off between the empirical error103 and the complexity term.104
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 = Ab(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 hyperposteriorQ from the learning process. The quality of the hyperposteriorQ is measured by the expected task error of learning new tasks using priors generated from it, which is formulated as:
er(Q) = EP∼QE(D,m)∼τ,S∼Dmer(Q = Ab(S, P )). (2)
Accordingly, the empirical counterpart of the above quantity is given by:
êr(Q) = EP∼Q 1
n n∑ i=1 êr(Q = Ab(Si, P )). (3)
3 PAC-BAYES META-LEARNING BOUND WITH GAUSSIAN RANDOMIZATION105
Based on the above definition, Pentina & Lampert (2014) and Amit & Meir (2018) present meta-106 learning PAC-Bayes generalization bounds w.r.t. hyperposteriorQ by using McAllester’s single-task107 bound (McAllester, 1999). Here we present a new meta-learning generalization bound with Gaus-108 sian randomization by using Catoni’s bound in Eq. (1). In particular, the classifier h is parameterized109 as hw with w ∈ Rdw . The prior and posterior is a distribution over the set of all possible parameters110 w. We choose both the prior P and posterior Q to be spherical Gaussians, i.e. P = N (wP , σ2wIdw)111 and Q = N (wQ, σ2wIdw). The mean wP is a random variable distributed first according to the112 hyperprior P , which we formulate asN (0, σ2wIdw), and later according to hyperposteriorQ, which113 we model as N (wQ, σ2wIdw). When encountering a new task i, we first sample the mean of prior114
wPi from the hyperposterior N (wQ, σ2wIdw), and then use it as a basis to learn the mean of poste-115 rior wQi = Ab(Si, P ), as shown in Figure 1(left). Then, we could derive the following PAC-Bayes116 meta-learning bound.117 Theorem 2. Consider the Meta-Learning (ML) framework, given the hyperprior P = N (0, σ2vIdv), then for any hyperposterior Q, any c1, c2 > 0 and any δ ∈ (0, 1] with probability ≥ 1− δ we have,
er(Q) ≤c′1c′2êr(Q) + ( n∑ i=1
c′1c ′ 2
2c2nmiσ2w + c′1 2c1nσ2w )‖wQ‖2 + n∑ i=1
c′1c ′ 2
2c2nmiσ2w ‖ E wP wQi −w Q‖2
+ n∑ i=1 c′1c ′ 2 c2nmiσ2w ( 1 2 + log 2n δ ) + c′1 c1nσ2w log 2 δ , (4)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 .118
Proof. See Appendix B.3 for the proof.119
Notice that the expected task generalization error is bounded by the empirical multi-task error plus120 two complexity terms. The first term demonstrates the environment-complexity which converges121 to zero if an infinite number of tasks are observed from the task environment (n → ∞), while the122 second is the task-complexity of the observed tasks which converges to zero when the sufficient123 samples in each task is observed (mi → ∞). Besides, the derived bound converges at the rate124 of O( 1m ) instead of O( 1√ m
) in (Pentina & Lampert, 2014; Amit & Meir, 2018), due to the use of125 Catoni’s bound.126
4 PAC-BAYES LOCALIZED META-LEARNING127
4.1 OVERALL FRAMEWORK128
Our motivation stems from a core challenge in PAC-Bayes meta-learning bound in 41, wherein the129 complexity term ∑n i=1 c′1c ′ 2 2c2nmiσ2w ‖EwQi − wQ‖2 is typically vital to the bound and so finding the130 tightest possible bound generally depends on minimizing this term. It is obvious that the optimal131
wQ is ∑n i=1 c′1c ′ 2Ew Q i
2c2nmiσ2w . However, if the learned posteriors for each task are mutually exclusive, i.e.,132 one learned posterior has a negative effect on another task, this term could be inevitably large.133
wQ is the mean of hyperposterior Q and this term naturally indicates the divergence between the134 mean of prior wPi sampled from the hyperposterior Q and the mean of posterior w Q i in each task.135 Therefore, we propose to adaptively choose the mean of prior wPi according to task i. It is obvious136 that the complexity term vanishes if we set wPi = w Q i , but the prior Pi in each task has to be137 chosen independently of the sample set Si. Fortunately, the PAC-Bayes theorem allows us to choose138 prior upon the data distribution Di. Therefore, we propose a prior predictor Φ : Dm → wP which139 receives task data distribution Dm and outputs the mean of prior wP . In this way, the generated140 priors could focus locally on those regions of model parameters that are of particular interest in141 solving specific tasks.142
Particularly, the prior predictor is parameterized as Φv with v ∈ Rdv . We abuse notation P and143 Q and assume v as a random variable distributed first according to the hyperprior P , which we144 reformulate as N (0, σ2vIdv), and later according to hyperposterior Q, which we reformulate as145 N (vQ, σ2vIdv). Given a new task i, we first sample v from hyperposterior N (vQ, σ2vIdv) and146 estimate the mean of prior wPi by leveraging prior predictor w P i = Φv(D m i ). Then, the base147 learner utilizes the sample set Si and the prior Pi = N (wPi , σ2wIdw) to produce a mean posterior148 wQi = Ab(Si, Pi), as illustrated in Figure 1(right).149
4.2 LCC-BASED PRIOR PREDICTOR150
To make wP close to wQ in each task, the prior predictor is required to (i) uncover the tight relation-151 ship between the sample set and model parameter. Intuitively, features and parameters yield similar152 local and global structures in their respective spaces in the classification problem. Features in the153
same category tend to be spatially clustered together while maintaining the separation between dif-154 ferent classes. Take linear classifiers as an example, let wk be the parameters w.r.t. category k, the155 separability between classes is implemented as x ·wk, which also explicitly encourages intra-class156 compactness. A reasonable choice of wk is to maximize the inner product distance with the input157 features in the same category and minimize the distance with the input features of the non-belonging158 categories. Besides, the prior predictor should be (ii) category-agnostic since it will be used contin-159 uously as new tasks and hence new categories become available. Lastly, it should be (iii) invariant160 under permutations of its inputs.161
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 wi = [wi[1], . . . ,wi[k], . . . ,wi[K]]. The prior predictor for class k could be defined as:
wPi [k] = Φv(D mik ik ) = E
Sik∼D mik ik
1
mik ∑ xj∈Sik φv(xj), (5)
where φv(·) : Rd → Rdw is the feature embedding function, mik is the number of samples belonging to category k, Sik and Dik are the sample set and data distribution for category k in task i. We call this function the expected prior predictor. Since data distribution Dik is considered unknown and our only insight as to Dik is through the sample set Sik, we approximate the expected prior predictor by its empirical counterpart, based on mik observed samples in the category k:
ŵPi [k] = Φ̂v(Sik) = 1
mik ∑ xj∈Sik φv(xj), (6)
which we call the empirical prior predictor. Although we can implement the embedding func-162 tion φv(·) with a multilayer perceptron (MLP), both input x and model parameter w are high-163 dimensional, making the empirical prior predictor Φ̂v(·) difficult to learn. According to Definition164 (3), any points on the latent manifold can be approximated by a linear combination of a set of anchor165 points. Inspired by this, if the anchor points are sufficiently localized, the empirical prior predic-166 tor Φ̂v(S) can also be approximated by a linear function w.r.t. a set of codings. Accordingly, we167 propose an LCC-based prior predictor, which is defined as:168
w̄Pi [k] = Φ̄v(Sik) = 1
mik ∑ xj∈Sik ∑ u∈C γu(xj)Φv(u), (7)
where Φv(u) ∈ Rdw is the feature embedding of base u ∈ Rd. As such, the pa-169 rameters of LCC-based prior predictor w.r.t. category k can be represented as vk =170 [Φvk(u1),Φvk(u2), . . . ,Φvk(u|C|)]. Lemma 1 illustrates the approximation error.
171
Lemma 1. (Empirical Pior Predictor Approximation) Given the definition of ŵPi [k] and w̄Pi [k] in Eq. (6) and Eq. (7), let (γ,C) be an arbitrary coordinate coding on Rd and φ be an (α, β)-Lipschitz smooth function. We have for all x ∈ Rd
‖ŵPi [k]− w̄Pi [k]‖ ≤ 1
mik ∑ xj∈Sik ( α‖xj − x̄j‖+ β ∑ u∈C ‖x̄j − u‖2 ) = Oα,β(γ,C), (8)
where x̄j = ∑ u∈C γu(xj)u. Then given any > 0, there exists a coding (γ,C) such that
|C| ≤ (1 + dM)N ( ,M), Oα,β(γ,C) ≤ [αcM + (1 + 5 √ dM)β] 2. (9)
Proof. See appendix B.1 for the proof.172
The first inequality of Lemma 1 demonstrates that a good LCC-based prior predictor should make x173 close to its physical approximation x̄ and should be localized. The second and third inequality show174 that if a set of anchor points C has cardinality O(dMN ( ,M)), emprical prior predictor can be175 linearly approximated using LCC up to accuracy O( √ dM
2). The complexity of the LCC coding176 scheme depends only on the number of anchor points |C| instead of the input dimension. In fact, a177 small |C| is usually sufficient to achieve good approximation.178 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:
arg min γ,C n∑ i=1 ∑ xj∈Si α‖xj − x̄j‖2 + β ∑ u∈C ‖xj − u‖2 s.t. ∑ u∈C γu(x) = 1,∀x, (10)
where x̄ = ∑
u∈C γu(x)u. In practice, we update C and γ by alternately optimizing a LASSO179 problem and a least-square regression problem, respectively.180
4.3 PAC-BAYES LOCALIZED META-LEARNING BOUND WITH GAUSSIAN RANDOMIZATION181
In order to derive a PAC-Bayes generalization bound for localized meta-learning, we first bound the182 approximation error between expected prior predictor and LCC-based prior predictor.183 Lemma 2. Given the definition of wP and w̄P in Eq. (5) and (7), let X be a compact set with radius R, i.e., ∀x,x′ ∈ X , ‖x− x′‖ ≤ R. For any δ ∈ (0, 1] with probability ≥ 1− δ, we have
‖wP − w̄P ‖2 ≤ K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 1 δ )) +Oα,β(γ,C) )2 . (11)
Proof. See appendix B.2 for the proof.184
Lemma 2 shows that the approximation error between expected prior predictor and LCC-based185 prior predictor depends on (i) the concentration of prior predictor and (ii) the quality of LCC coding186 scheme. The first term implies the number of samples for each category should be larger for better187 approximation. This is consistent with the results of estimating the center of mass (Cristianini &188 Shawe-Taylor, 2004). Based on Lemma 2, we have the following PAC-Bayes LML bound.189 Theorem 3. Consider the Localized Meta-Learning (LML) framework, give the hyperprior P = N (0, σ2vIdv), then for any hyperposterior Q, any c1, c2 > 0 and any δ ∈ (0, 1] with probability ≥ 1− δ we have,
er(Q) ≤c′1c′2êr(Q) + ( n∑ i=1
c′1c ′ 2
2c2nmiσ2v + c′1 2c1nσ2v )‖vQ‖2 + n∑ i=1 c′1c ′ 2 c2nmiσ2w ‖E v wQi − Φ̄vQ(Si)‖ 2
+ n∑ i=1 c′1c ′ 2 c2nmiσ2w  1 σ2w K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 4n δ )) +Oα,β(γ,C) )2 + dwK( σv σw )2  +
n∑ i=1 c′1c ′ 2 c2nmiσ2w log 4n δ + c′1 2c1nσ2v log 2 δ , (12)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 . To get a better understanding, we further simplify the notation and obtain that
er(Q) ≤c′1c′2êr(Q) + ( n∑ i=1
c′1c ′ 2
2c2nmiσ2v + c′1 2c1nσ2v )‖vQ‖2 + n∑ i=1 c′1c ′ 2 c2nmiσ2w ‖E v wQi − Φ̄vQ(Si)‖ 2
+ const(α, β,R, δ, n,mi). (13)
Proof. See appendix B.3 for the proof.190
Similarly with the PAC-Bayes meta-learning bound in Theorem 2 and the bounds in (Pentina &191 Lampert, 2014; Amit & Meir, 2018), the expected task error er(Q) is bounded by the empirical192 task error êr(Q) plus the task-complexity and environment-complexity terms. The main innovation193 here is to exploit the potential to choose the mean of prior wP based on task data S. Intuitively, if194 the selection of the LCC-based prior predictor is appropriate, it will narrow the divergence between195 the mean of prior wPi sampled from the hyperposterior Q and the mean of posterior w Q i in each196 task. Therefore, the bound can be tighter than the ones in the meta-learning framework. Our em-197 pirical study in Section 5 illustrates that the algorithms derived from this bound can achieve better198 performance than the methods derived from standard PAC-Bayes meta-learning bounds.199
When one is choosing the LCC-based prior predictor Φ̄v(·), the number of anchor points |C|, there200 is a balance between accuracy and simplicity. As we increase |C|, it will essentially increase the201 expressive power of Φ̄v(·) and reduce the complexity term ‖E
v wQ − Φ̄vQ(S)‖2. However, at the202 same time, it will increase the complexity term ‖vQ‖2 and make the bound loose. If we set |C| to203 1, it is degraded to the regular meta-learning framework.204
4.4 LOCALIZED META-LEARNING ALGORITHM205
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 (vQ, σ2vIdv), so the mean of prior wP sampled from the learned hyperposterior work well for future tasks. The PAC-Bayes localized meta-learning bound in (27) can be compactly written as
n∑ i=1 E v êri(Qi = Ab(Si, P )) + α1‖vQ‖2 + n∑ i=1 α2 mi ‖E v wQi − Φ̄vQ(Si)‖ 2, (14)
where α1, α2 > 0 are hyperparameters. For task i, the learning algorithm Ab(·) can be formulated as w?i = arg min
wQi
E v êri(Qi = N (wQi , σ2wIdw)). Following Amit & Meir (2018), we jointly opti-
mize the parameters of LCC-based prior predictor v and the parameters of classifiers in each task w1,w2, . . . ,wn, which is formulated as
arg min v,w1,...,wn n∑ i=1 E v êri(wi) + α1‖vQ‖2 + n∑ i=1 α2 mi ‖E v wQi − Φ̄vQ(Si)‖ 2. (15)
We can optimize v and w via mini-batch SGD. The details of algorithms for meta-training are206 given in Algorithms 1. The expectation over Gaussian distribution and its gradient can be efficiently
Algorithm 1 Localized Meta-Learning (LML) algorithm Input: Data sets of observed tasks: S1, . . . , Sn. Output: Learned prior predictor Φ̄ parameterized by v. Initialize v ∈ Rdv and wi ∈ Rdw 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 ⊂ Si. Approximate E
v êri(wi) using S′i.
end for Compute the objective in (15), i.e. J ← ∑n i=1 Ev êri(wi) + α1‖v Q‖2 + ∑n i=1 α2 mi ‖E v wQi − Φ̄vQ(Si)‖2. Evaluate the gradient of J w.r.t. {v,w1, . . . ,wn} using backpropagation. Take an optimization step.
end while 207 estimated by using the re-parameterization trick (Kingma & Welling, 2014; Rezende et al., 2014).208 For example, to sample w from the posterior Q = N (wQ, σ2wIdw), we first draw ξ ∼ N (0, Idw)209 and then apply the deterministic function wQ + ξ σ, where is an element-wise multiplication.210
5 EXPERIMENTS211
5.1 DATASETS AND SETUP212
We use CIFAR-100 and Caltech-256 in our experiments. CIFAR-100 (Krizhevsky, 2009) contains213 60,000 images from 100 fine-grained categories and 20 coarse-level categories. As in (Zhou et al.,214
2018), we use 64, 16, and 20 classes for meta-training, meta-validation, and meta-testing, respec-215 tively. Caltech-256 has 30,607 color images from 256 classes (Griffin et al., 2007). Similarly, we216 split the dataset into 150, 56 and 50 classes for meta-training, meta-validation, and meta-testing. We217 consider 5-way classification problem. Each task is generated by randomly sampling 5 categories218 and each category contains 50 samples. The base model uses the convolutional architecture in (Finn219 et al., 2017), which consists of 4 convolutional layers, each with 32 filters and a fully-connected220 layer mapping to the number of classes on top. High dimensional data often lies on some low di-221 mensional manifolds. We utilize an auto-encoder to extract the semantic information of image data222 and then construct the LCC scheme based on the embeddings. The parameters of prior predictor and223 base model are random perturbations in the form of Gaussian distribution. We design two different224 meta-learning environment setting to validate the efficacy of the proposed method. The first one uses225 the pre-trained base model as an initialization, which utilizes all the meta-training classes (64-class226 classification in CIFAR-100 case) to train the feature extractor. The second one uses the random227 initialization. We compare the proposed LML method with ML-PL method (Pentina & Lampert,228 2014), ML-AM method (Amit & Meir, 2018) and ML-A which is derived from Theorem 2. In these229 methods, we use their main theorems about the PAC-Bayes generalization bound to derive the objec-230 tive for the algorithm. We also compare with two typical meta-learning few-shot learning methods:231 MAML (Finn et al., 2017) and MatchingNet (Vinyals et al., 2016). To ensure a fair comparison, all232 approaches adopt the same network architecture and pre-trained feature extractor.233
5.2 RESULTS234
In Figure 3, we demonstrate the average test error of learning a new task based on the number of235 training tasks in different settings (with or without a pre-trained feature extractor). It is obvious236 that the performance continually increases as we increase the number of training tasks for all the237 methods. This is consistent with the generalization bounds that the complexity term converges to238 zero if large numbers of tasks are observed. ML-A consistently outperforms ML-PL and ML-AM239 since the bound w.r.t. ML-A in Theorem 2 converges at the rate of O( 1m ) while the bounds w.r.t.240 ML-PL and ML-AM converge at the rate ofO( 1√
m ). This demonstrates the importance of using tight241 generalization bound. Our proposed LML significantly outperforms the baselines, which validates242 the effectiveness of the proposed LCC-based prior predictor. It is a more suitable representation for243 meta-knowledge than the traditional global hyperposterior in ML-A, ML-AM, and ML-PL.244
Moreover, we can find that all PAC-Bayes baselines outperform MAML and MatchingNet. Note245 that MAML and MatchingNet adopt the episodic training paradigm to solve the few-shot learn-246 ing problem. The meta-training process requires millions of tasks and each task contains limited247 samples, which is not the case in our experiment. Scarce tasks in meta-training leads to severely248 meta-overfitting. In our method, the learned prior serves both as an initialization of base model and249 as a regularizer which restricts the solution space while allowing variation based on specific task250 data. It yields a model with smaller error than its unbiased counterpart when applied to a similar251 task.252
Finally, we observe that if the pre-trained feature extractor is provided, all of these methods do better253 than meta-training with random initialization. This is because pre-trained feature extractor can be254 regarded as a data-dependent hyperpior. It is closer to the hyperposteior than the randomly initialized255 hyperprior. Therefore, it reduces the environment complexity term and improves the generalization256 performance.257
In Figure 4(b), we show the divergence between the mean of generated prior wP from meta model258 and the mean of learned posterior wQ for LML and ML-A. This further validates the effectiveness259 of the LCC-based prior predictor which could narrow the divergence term and thus tight the bound.260 In Figure 4(a), we vary the number of bases |C| in LCC scheme from 4 to 256, the optimal value is261 around 64 in both datasets. This indicates that LML is sensitive to the number of bases |C|, which262 further affects the quality of LCC-based prior predictor and the performance of LML.263
6 RELATED WORK264
Meta-Learning. Meta-learning literature commonly considers the empirical task error by directly265 optimizing a loss of meta learner across tasks in the training data. Recently, this has been success-266
fully applied in a variety of models for few-shot learning (Ravi & Larochelle, 2017; Snell et al.,267 2017; Finn et al., 2017; Vinyals et al., 2016). Although Vuorio et al. (2018); Rusu et al. (2019);268 Zintgraf et al. (2019); Wang et al. (2019) consider task adaptation when using meta-knowledge for269 specific tasks, all of them are not based on generalization error bounds, which is the focus of our270 work. Meta-learning in the online setting has regained attention recently (Denevi et al., 2018b;a;271 2019; Balcan et al., 2019), in which online-to-batch conversion results could imply generalization272 bounds. Galanti et al. (2016) analyzes transfer learning in neural networks with PAC-Bayes tools.273 Most related to our work are (Pentina & Lampert, 2014; Amit & Meir, 2018) which provide a274 PAC-Bayes generalization bound for meta-learning framework. In contrast, neither work considers275 localized meta-knowledge for specific tasks.276
Localized PAC-Bayes Learning. There has been a prosperous line of research for learning priors277 to improve the PAC-Bayes bounds Catoni (2007); Guedj (2019). (Parrado-Hernández et al., 2012)278 showed that priors can be learned by splitting the available training data into two parts, one for279 learning the prior, one for learning the posterior. (Lever et al., 2013) derived an expression for the280 overall best prior, i.e. the distribution resulting in the smallest possible bound value and bounded281 the KL divergence by a term independent of data distribution. Recently, (Rivasplata et al., 2018)282 bounded the KL divergence by investigating the stability of the hypothesis. (Dziugaite & Roy, 2018)283 optimized the prior term in a differentially private way. In summary, theses methods construct some284 quantities that reflect the underlying data distribution, rather than the sample set, and then choose285 the prior P based on these quantities. These works, however, are only applicable for single-task286 problem and could not transfer knowledge across tasks in meta-learning setting.287
7 CONCLUSION288
This work contributes a novel localized meta-learning framework from a theoretical perspective. We289 propose a generalization bound based on PAC-Bayes theory with Gaussian randomization. Instead290 of formulating meta-knowledge as a global distribution, we propose an LCC-based prior predictor291 to output local meta-knowledge by using task information. We further develop a practical algorithm292 with deep neural network based on the bound. An interesting topic for future work would be to293 explore other principle to construct the prior predictor and apply the localized meta-learning frame-294 work to a more realistic scenario that tasks are sampled non-i.i.d. from an environment. Another295 challenging problem is to extend our techniques to derive localized meta-learning algorithms for296 regression and reinforcement learning problem.297
REFERENCES298 Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-Bayes theory.299 In International Conference on Machine Learning, pp. 205–214, 2018.300
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient-301 based meta-learning. In Proceedings of the 36th International Conference on Machine Learning,302 ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 424–433, 2019.303
Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12:304 149–198, 2000.305
Luca Bertinetto, João F Henriques, Jack Valmadre, Philip Torr, and Andrea Vedaldi. Learning feed-306 forward one-shot learners. In Advances in Neural Information Processing Systems, pp. 523–531,307 2016.308
O Catoni. PAC-Bayesian supervised classification: The thermodynamics of statistical learning.309 institute of mathematical statistics lecture notes—monograph series 56. IMS, Beachwood, OH.310 MR2483528, 2007.311
Nello Cristianini and John Shawe-Taylor. Kernel methods for pattern analysis, volume 173. Cam-312 bridge University Press Cambridge, 2004.313
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to-314 learn with statistical guarantees. In Proceedings of the Thirty-Fourth Conference on Uncertainty315
in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pp. 457–466,316 2018a.317
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around318 a common mean. In Advances in Neural Information Processing Systems, pp. 10169–10179,319 2018b.320
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-learn321 stochastic gradient descent with biased regularization. In Proceedings of the 36th International322 Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA,323 pp. 1566–1575, 2019.324
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent PAC-Bayes priors via differential325 privacy. In Advances in Neural Information Processing Systems, pp. 8430–8441, 2018.326
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation327 of deep networks. In Proceedings of the 34th International Conference on Machine Learning-328 Volume 70, pp. 1126–1135. JMLR. org, 2017.329
Tomer Galanti, Lior Wolf, and Tamir Hazan. A theoretical framework for deep transfer learning.330 Information and Inference: A Journal of the IMA, 5(2):159–209, 2016.331
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. Pac-bayesian learn-332 ing of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine333 Learning, pp. 353–360. ACM, 2009.334
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.335
Benjamin Guedj. A primer on pac-bayesian learning. arXiv preprint arXiv:1901.05353, 2019.336
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter-337 national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9,338 2015, Conference Track Proceedings, 2015.339
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International340 Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014,341 Conference Track Proceedings, 2014.342
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer,343 2009.344
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter PAC-Bayes bounds through345 distribution-dependent priors. Theoretical Computer Science, 473:4–28, 2013.346
Andreas Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research,347 6(Jun):967–994, 2005.348
David A McAllester. PAC-Bayesian model averaging. In Proceedings of the twelfth annual confer-349 ence on Computational learning theory, pp. 164–170. ACM, 1999.350
Thomas Mensink, Jakob Verbeek, Florent Perronnin, and Gabriela Csurka. Distance-based image351 classification: Generalizing to new classes at near-zero cost. IEEE transactions on pattern anal-352 ysis and machine intelligence, 35(11):2624–2637, 2013.353
Emilio Parrado-Hernández, Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC-Bayes354 bounds with data dependent priors. Journal of Machine Learning Research, 13(Dec):3507–3531,355 2012.356
Anastasia Pentina and Christoph Lampert. A PAC-Bayesian bound for lifelong learning. In Inter-357 national Conference on Machine Learning, pp. 991–999, 2014.358
Siyuan Qiao, Chenxi Liu, Wei Shen, and Alan L. Yuille. Few-shot image recognition by predicting359 parameters from activations. In 2018 IEEE Conference on Computer Vision and Pattern Recog-360 nition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 7229–7238, 2018.361
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. In 5th Interna-362 tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017,363 Conference Track Proceedings, 2017.364
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and365 approximate inference in deep generative models. In Proceedings of the 31th International Con-366 ference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pp. 1278–1286,367 2014.368
Omar Rivasplata, Csaba Szepesvari, John S Shawe-Taylor, Emilio Parrado-Hernandez, and Shiliang369 Sun. PAC-Bayes bounds for stable algorithms with instance-dependent priors. In Advances in370 Neural Information Processing Systems, pp. 9214–9224, 2018.371
Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osin-372 dero, and Raia Hadsell. Meta-learning with latent embedding optimization. In 7th International373 Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019,374 2019.375
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In376 Advances in Neural Information Processing Systems, pp. 4077–4087, 2017.377
Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012.378
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one379 shot learning. In Advances in neural information processing systems, pp. 3630–3638, 2016.380
Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim. Toward multimodal model-agnostic381 meta-learning. arXiv preprint arXiv:1812.07172, 2018.382
Xin Wang, Fisher Yu, Ruth Wang, Trevor Darrell, and Joseph E Gonzalez. Tafe-net: Task-aware383 feature embeddings for low shot learning. In Proceedings of the IEEE Conference on Computer384 Vision and Pattern Recognition, pp. 1831–1840, 2019.385
Flood Sung Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales.386 Learning to compare: Relation network for few-shot learning. In Proc. of the IEEE Conference387 on Computer Vision and Pattern Recognition (CVPR), Salt Lake City, UT, USA, 2018.388
Kai Yu, Tong Zhang, and Yihong Gong. Nonlinear learning using local coordinate coding. In389 Advances in neural information processing systems, pp. 2223–2231, 2009.390
Fengwei Zhou, Bin Wu, and Zhenguo Li. Deep meta-learning: Learning to learn in the concept391 space. arXiv preprint arXiv:1802.03596, 2018.392
Luisa M. Zintgraf, Kyriacos Shiarlis, Vitaly Kurin, Katja Hofmann, and Shimon Whiteson. Fast393 context adaptation via meta-learning. In Proceedings of the 36th International Conference on394 Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 7693–7702,395 2019.396
This supplementary document contains the technical proofs of theoretical results and details of ex-397 periments. It is structured as follows: Appendix A present notations for prior predictor. Appendix B398 gives the proofs of the main results. Appendix B.1 and B.2 show the approximation error between399 LCC-based prior predictor and empirical prior predictor, expected prior predictor, respectvely. They400 are used in the proof of Theorem 3. Next, in Appendix B.3 and B.4 we show the PAC-Bayes gener-401 alization bound of localized meta-learning in Theorem 3 and also provides the PAC-Bayes general-402 ization bound of regular meta-learning in Theorem 2. Finally, details of experiments are presented403 in Appendix C.404
A NOTATIONS405
Let φv(·) : Rd → Rdw be the feature embedding function. mik denotes the number of samples belonging to category k. Sik and Dik 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:
wPi [k] = Φv(D mik ik ) = E
Sik∼D mik ik
1
mik ∑ xj∈Sik φv(xj).
The empirical prior predictor w.r.t. class k in task i is defined as:
ŵPi [k] = Φ̂v(Sik) = 1
mik ∑ xj∈Sik φv(xj).
The LCC-based prior predictor w.r.t. class k in task i is defined as:
w̄Pi [k] = Φ̄v(Sik) = 1
mik ∑ xj∈Sik ∑ u∈C γu(xj)Φv(u).
B THEORETICAL RESULTS406
B.1 PROOF OF LEMMA 1407
This lemma bounds the error between the empirical prior predictor ŵPi [k] and the LCC-based prior408 predictor w̄Pi [k].409
Lemma 1 Given the definition of ŵPi [k] and w̄Pi [k] in Eq. (6) and Eq. (7), let (γ,C) be an arbitrary coordinate coding on Rdx and φ be an (α, β)-Lipschitz smooth function and . We have for all x ∈ Rdx
‖ŵPi [k]− w̄Pi [k]‖ ≤ 1
mik ∑ xj∈Sik ( α‖xj − x̄j‖+ β ∑ u∈C ‖x̄j − u‖2 ) = Oα,β(γ,C), (16)
where x̄j = ∑ u∈C γu(xj)u. Then given any > 0, there exists a coding (γ,C) such that
|C| ≤ (1 + dM)N ( ,M), Oα,β(γ,C) ≤ [αcM + (1 + 5 √ dM)β] 2. (17)
Proof. Let x̄j = ∑ u∈C γu(xj)u. We have
‖Φ̂v(Sik)− Φ̄v(Sik)‖2
= 1
mik ∑ xj∈Sik ‖Φv(xj)− ∑ u∈C γu(xj)Φv(u)‖2
≤ 1 mik ∑ xj∈Sik ( ‖Φv(xj)− Φv(x̄j)‖2 + ‖ ∑ u∈C γu(xj)(Φv(u)− Φv(x̄j)‖2 )
= 1
mik ∑ xj∈Sik ( ‖Φv(xj)− Φv(x̄j)‖2 + ‖ ∑ u∈C γu(xj)(Φv(u)− Φv( ∑ u∈C γu(xj)u))−∇Φv(x̄j)(u− x̄j)‖2 )
≤ 1 mik ∑ xj∈Sik ( ‖Φv(xj)− Φv(x̄j)‖2 + ∑ u∈C |γu(xj)|‖(Φv(u)− Φv( ∑ u∈C γu(xj)u))−∇Φv(x̄j)(u− x̄j)‖2 )
≤ 1 mik ∑ xj∈Sik ( α‖xj − x̄j‖2 + β ∑ u∈C ‖x̄j − u‖22 ) = Oα,β(γ,C)
In the above derivation, the first inequality holds by the triangle inequality. The second equality410 holds since ∑ u∈C γu(xj) = 1 for all xj . The last inequality uses the assumption of (α, β)-Lipschitz411 smoothness of Φv(·).412 According to the Manifold Coding Theorem in (Yu et al., 2009), if the data points x lie on a compact smooth manifoldM. Then given any > 0, there exists anchor points C ⊂ M and coding γ such that
|C| ≤ (1 + dM)N ( ,M), 1
mik ∑ xj∈Sik ( α‖xj − x̄j‖2 + β ∑ u∈C ‖x̄j − u‖22 ) ≤ [αcM + (1 + 5 √ dM)β] 2. (18)
This implies the desired bound.413
The first inequality of this lemma demonstrates that the quality of LCC approximation is bounded414 by two terms: the first term ‖xj − x̄j‖2 indicates x should be close to its physical approximation415 x̄, the second term ‖x̄j − u‖ implies that the coding should be localized. The second and third416 inequality show that the approximation error of local coordinate coding depends on the intrinsic di-417 mension of the manifold instead of the dimension of input. If a set of anchor pointsC has cardinality418 O(dMN ( ,M)), emprical prior predictor can be linearly approximated using LCC up to accuracy419 O( √ dM 2).420
B.2 PROOF OF LEMMA 2421
In order to proof Lemma 2, we first introduce a relevant theorem.422 Theorem 4. (Vector-valued extension of McDiarmid’s inequality (Rivasplata et al., 2018)) Let X1, . . . ,Xm ∈ X be independent random variables, and f : Xm → Rdw be a vector-valued mapping function. If, for all i ∈ {1, . . . ,m}, and for all x1, . . . ,xm,x′i ∈ X , the function f satisfies
sup xi,x′i
‖f(x1:i−1,xi,xi+1:m)− f(x1:i−1,x′i,xi+1:m)‖ ≤ ci (19)
Then E‖f(X1:m) − E[f(X1:m)]‖ ≤ √∑m i=1 c 2 i . For any δ ∈ (0, 1) with probability ≥ 1 − δ we have
‖f(X1:m)− E[f(X1:m)]‖ ≤ √√√√ m∑ i=1 c2i + √∑m i=1 c 2 i 2 log( 1 δ ). (20)
The above theorem indicates that bounded differences in norm implies the concentration of f(X1:m)423 around its mean in norm, i.e., ‖f(X1:m)− E[f(X1:m)]‖ is small with high probability.424
Then, we bound the error between expected prior predictor wPi and the empirical prior predictor425 ŵPi .426
Lemma 3. Given the definition of wPi [k] and ŵPi [k] in (5) and (6), let X be a compact set with radius R, i.e., ∀x,x′ ∈ X , ‖x− x′‖ ≤ R. For any δ ∈ (0, 1] with probability ≥ 1− δ, we have
‖wPi [k]− ŵPi [k]‖ ≤ αR √ mik (1 +
√ 1
2 log(
1 δ )). (21)
Proof. According to the definition of Φ̂v(·) in (6), for all points x1, . . . ,xj−1,xj+1, . . . ,xmk ,x′j in the sample set Sik, we have
sup xi,x′i
‖Φ̂v(x1:j−1,xj ,xj+1:mk)− Φ̂v(x1:j−1,x′j ,xj+1:mk)‖
= 1
mik sup xj ,x′j
‖Φv(xj)− Φv(x′j)‖ ≤ 1
mik sup xj ,x′j
α‖xj − x′j‖ ≤ αR
mik , (22)
whereR denotes the domain of x, sayR = supx ‖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
‖wPi [k]− ŵPi [k]‖ = ‖Φ̂v(Sik)− E[Φ̂v(Sik)]‖ ≤ αR √ mik (1 +
√ 1
2 log(
1 δ )). (23)
This implies the bound.427
Lemma 3 shows that the bounded difference of function Φv(·) implies its concentration, which can428 be further used to bound the differences between empirical prior predictor w̄Pi [k] and expected prior429 predictor wPi [k]. Now, we bound the error between expected prior predictor w P i and the LCC-based430 prior predictor w̄Pi .431
Lemma 2 Given the definition of wPi and w̄Pi in (5) and (7), let X be a compact set with radius R, i.e., ∀x,x′ ∈ X , ‖x− x′‖ ≤ R. For any δ ∈ (0, 1] with probability ≥ 1− δ, we have
‖wPi − w̄Pi ‖2 ≤ K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 1 δ )) +Oα,β(γ,C) )2 . (24)
Proof According to the definition of wP , w̄P and ŵP , we have
‖wPi − w̄Pi ‖2
= K∑ k=1 ‖wPi [k]− w̄Pi [k]‖2
= K∑ k=1 ‖E[Φ̂v(Sik)]− Φ̂v(Sik) + Φ̂v(Sik)− Φ̄v(Sik)‖2
= K∑ k=1 ( ‖E[Φ̂v(Sik)]− Φ̂v(Sik)‖2 + ‖Φ̂v(Sik)− Φ̄v(Sik)‖2 + 2(E[Φ̂v(Sik)]− Φ̂v(Sik))>(Φ̂v(Sik)− Φ̄v(Sik)) ) ≤
K∑ k=1 ( ‖E[Φ̂v(Sik)]− Φ̂v(Sik)‖2 + ‖Φ̂v(Sik)− Φ̄v(Sik)‖2 + 2‖E[Φ̂v(Sik)]− Φ̂v(Sik)‖‖Φ̂v(Sik)− Φ̄v(Sik)‖ ) .
(25)
Substitute Lemma 3 and Lemma 1 into the above inequality, we can derive
PSik∼Dmkk ‖wP − w̄P ‖2 ≤ K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 1 δ )) +Oα,β(γ,C) )2 ≥ 1− δ. (26)
This gives the assertion.432
Lemma 2 shows that the approximation error between expected prior predictor and LCC-based prior433 predictor depends on the number of samples in each category and the quality of the LCC coding434 scheme.435
B.3 PROOF OF THEOREM 3436
Theorem 3 Let Q be the posterior of base learner Q = N (wQ, σ2wIdw) and P be the prior N (Φ̄v(S), σ2wIdw). 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 learnerQ = N (vQ, σ2vIdv). Give the hyperprior P = N (0, σ2vIdv), then for any hyperposterior Q, any c1, c2 > 0 and any δ ∈ (0, 1] with probability ≥ 1− δ we have, er(Q) ≤c′1c′2êr(Q) + ( n∑ i=1 c′1c ′ 2 2c2nmiσ2v + c′1 2c1nσ2v )‖vQ‖2 + n∑ i=1 c′1c ′ 2 c2nmiσ2w ‖E v wQi − Φ̄vQ(Si)‖ 2
+ n∑ i=1 c′1c ′ 2 c2nmiσ2w  1 σ2w K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 4n δ )) +Oα,β(γ,C) )2 + dwK( σv σw )2  +
n∑ i=1 c′1c ′ 2 c2nmiσ2w log 4n δ + c′1 2c1nσ2v log 2 δ , (27)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 . We can simplify the notation and obtain that
er(Q) ≤c′1c′2êr(Q) + ( n∑ i=1
c′1c ′ 2
2c2nmiσ2v + c′1 2c1nσ2v )‖vQ‖2 + n∑ i=1 c′1c ′ 2 c2nmiσ2w ‖E v wQi − Φ̄vQ(Si)‖ 2
+ const(α, β,R, δ, n,mi). (28)
Proof Our proof contains two steps. First, we bound the error within observed tasks due to ob-437 serving a limited number of samples. Then we bound the error on the task environment level due438 to observing a finite number of tasks. Both of the two steps utilize Catoni’s classical PAC-Bayes439 bound (Catoni, 2007) to measure the error. We give here a general statement of the Catoni’s classical440 PAC-Bayes bound.441
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 XG1 , {X1, . . . , XG} 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 X1, . . . , Xk). For any δ ∈ (0, 1], the following bounds holds uniformly for all posterior distribution ρ over F (even sample dependent),
PXK1 ∼i.i.dX
{ E
X∼X E f∼ρ g(f,X) ≤ c 1− e−c
[ 1
G G∑ g=1 E f∼ρ g(f,Xk) + KL(ρ||π) + log 1δ K × c
] ,∀ρ } ≥ 1− δ. (29)
First step We utilize Theorem 5 to bound the generalization error in each of the observed tasks.442 Let i ∈ 1, . . . , n be the index of task. For task i, we substitute the following definition into443 the Catoni’s PAC-Bayes Bound. Specifically, Xg , (xij , yij),K , mi denote the samples and444 X , Di denotes the data distribution. We instantiate the hypotheses with a hierarchical model445 f , (v,w), where v ∈ Rdv and w ∈ Rdw are the parameters of meta learner (prior predic-446 tor) Φv(·) and base learner h(·) respectively. The loss function only considers the base learner,447 which is defined as g(f,X) , `(hw(x), y). The prior over model parameter is represented448 as π , (P, P ) , (N (0, σ2vIdv),N (wP , σ2wIdw)), a Gaussian distribution (hyperprior of meta449
learner) centered at 0 and a Gaussian distribution (prior of base learner) centered at wP , respec-450 tively. We set the posterior to ρ , (Q, Q) , (N (vQ, σ2vIdv),N (wQ, σ2wIdw)), a Gaussian dis-451 tribution (hyperposterior of meta learner) centered at vQ and a Gaussian distribution (posterior of452 base learner) centered at wQ. According to Theorem 5, the generalization bound holds for any453 posterior distribution including the one generated in our localized meta-learning framework. Specif-454 ically, we first sample v from hyperposterior N (vQ, σ2vIdv) and estimate wP by leveraging ex-455 pected prior predictor wP = Φv(D). The base learner algorithm Ab(S, P ) utilizes the sample set456 S and the prior P = N (wP , σ2wIdw) to produce a posterior Q = Ab(S, P ) = N (wQ, σ2wIdw).457 Then we sample base learner parameter w from posterior N (wQ, σ2wIdw) and compute the in-458 curred loss `(hw(x), y). On the whole, meta-learning algorithm Am(S1, . . . , Sn,P) observes459 a series of tasks S1, . . . , Sn and adjusts its hyperprior P = N (vP , σ2vIdv) into hyperposterior460 Q = Am(S1, . . . , Sn,P) = N (vQ, σ2vIdv).461 The KL divergence term between prior π and posterior ρ is computed as follows:
KL(ρ‖π) = E f∼ρ
log ρ(f)
π(f) = E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) log N (vQ, σ2vIdv)N (wQ, σ2wIdw) N (0, σ2vIdv)N (wP , σ2wIdw)
= E v∼N (vQ,σ2vIdv ) log N (vQ, σ2vIdv) N (0, σ2vIdv) + E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) log N (wQ, σ2wIdw) N (wP , σ2wIdw)
= 1
2σ2v ‖vQ‖2 + E v∼N (vQ,σ2vIdv )
1
2σ2w ‖wQ −wP ‖2. (30)
In our localized meta-learning framework, in order to make KL(Q||P ) small, the center of prior distribution wP is generated by the expected prior predictor wP = Φv(D). However, the data distribution D is considered unknown and our only insight as to Dik is through the sample set Sik. In this work, we approximate the expected prior predictor Φv(D) with the LCC-based prior predictor w̄P = Φ̄v(S). Denote the term E
v∼N (vQ,σ2vIdv ) 1 2σ2w ‖wQ −wP ‖2 by E v 1 2σ2w ‖wQ −wP ‖2
for convenience, we have
E v
1
2σ2w ‖wQ −wP ‖2 =E v
1
2σ2w ‖wQ − w̄P + w̄P −wP ‖2
=E v
1
2σ2w [‖wQ − w̄P ‖2 + ‖w̄P −wP ‖2 + 2(wQ − w̄P )>(w̄P −wP )]
≤E v
1
2σ2w [‖wQ − w̄P ‖2 + ‖w̄P −wP ‖2 + 2‖wQ − w̄P ‖‖w̄P −wP ‖]
≤ 1 σ2w E v ‖wQ − Φ̄v(S)‖2 + 1 σ2w E v ‖w̄P −wP ‖2. (31)
Since w̄Pi = Φ̄v(Si) = [Φ̄v(Si1), . . . , Φ̄v(Sik), . . . , Φ̄v(SiK)], we have
E v ‖wQi − Φ̄v(Si)‖ 2 = K∑ k=1 E v ‖wQi [k]− Φ̄v(Sik)‖ 2
= K∑ k=1 ( E v ‖wQi [k]‖ 2 − 2(E v wQi [k]) >(Φ̄vQ(Sik)) + ‖Φ̄vQ(Sik)‖2 + V v [‖Φ̄v(Sik)‖] )
= K∑ k=1 ( ‖E v wQi [k]− Φ̄vQ(Sik)‖ 2 + dv |C| σ2v ) =‖E
v wQi − Φ̄vQ(Si)‖ 2 + dwKσ 2 v, (32)
where V v [‖Φ̄v(Sik)‖] denotes the variance of ‖Φ̄v(Sik)‖. The last equality uses the fact that dv = |C|dw. Combining Lemma 2, for any δ′ ∈ (0, 1] with probability ≥ 1− δ′ we have
E v
1
2σ2w ‖wQi −w P i ‖2
≤ 1 σ2w ‖E v wQi − Φ̄vQ(Si)‖ 2 + dwK( σv σw )2 + 1 σ2w K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 1 δ )) +Oα,β(γ,C) )2 (33)
Then, according to Theorem 5, we obtain that for any δi2 > 0
PSi∼Dmii
{ E
(x,y)∼Di E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) `(hw(x), y)
≤ c2 1− e−c2 · 1 mi mi∑ j=1 E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) `(hw(xj), yj)
+ 1
(1− e−c2) ·mi
( 1
2σ2v ‖vQ‖2 + E v∼N (vQ,σ2vIdv )
1
2σ2w ‖wQi −w P i ‖2 + log
2
δi
) ,∀Q } ≥ 1− δi
2 ,
(34)
for all observed tasks i = 1, . . . , n. Define δ′ = δi2 and combine inequality (33), we obtain
PSi∼Dmii
{ E
(x,y)∼Di E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) `(hw(x), y)
≤ c2 1− e−c2 · 1 mi mi∑ j=1 E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) `(hw(xj), yj)
+ 1 (1− e−c2)mi · ( 1 2σ2v ‖vQ‖2 + 1 σ2w ‖E v wQi − Φ̄vQ(Si)‖ 2 + log 2 δi + dwK( σv σw )2
+ 1
σ2w K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 2 δi )) +Oα,β(γ,C) )2) ,∀Q } ≥ 1− δi, (35)
Using the notations in Section 4, the above bound can be simplified as
PSi∼Dmii
{ E
v∼N (vQ,σ2vIdv ),wP =Φv(D),Pi=N (wP ,σ2wIdw ) er(Ab(Si, Pi))
≤ c2 1− e−c2 E v∼N (vQ,σ2vIdv ),wP =Φv(D),Pi=N (wP ,σ2wIdw ) êr(Ab(Si, Pi))
+ 1
(1− e−c2)mi
( 1
2σ2v ‖vQ‖2 + 1 σ2w ‖E v wQi − Φ̄vQ(Si)‖ 2 + log 2 δi + dwK( σv σw )2
+ 1
σ2w K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 2 δi )) +Oα,β(γ,C) )2) ,∀Q } ≥ 1− δi. (36)
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 (Di,mi, Si), i = 1, . . . , n, where (Di,mi) are sampled from the same meta distribution τ and Si ∼ Dmii . The hyposthesis is parameterized as Φv(D) with meta learner parameter v. The loss function is g(f,X) , E
(x,y)∼D E w∼N (wQ,σ2wIdw ) `(hw(x), y), where wQ = Ab(Si, Pi). Let π , N (0, σ2vIdv) be
the prior over meta learner parameter, the following holds for any δ0 > 0,
P(Dmii )∼τ,Si∼Dmii ,i=1,...,n
{ E
(D,m)∼τ E S∼Dm E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) E (x,y)∼Di `(hw(x), y)
≤ c1 1− e−c1 · 1 n n∑ i=1 E v∼N (vQ,σ2vIdv ) E w∼N (wQ,σ2wIdw ) E (x,y)∼Di `(hw(x), y)
+ 1
(1− e−c1)n
( 1
2σ2v ‖vQ‖2 + log 1 δ0
) ,∀Q } ≥ 1− δ0. (37)
Using the term in Section 4, the above bound can be simplified as
P(Dmii )∼τ,Si∼Dmii ,i=1,...,n
{ er(Q)
≤ c1 1− e−c1 · 1 n n∑ i=1 E v∼N (vQ,σ2vIdv ),wP =Φv(D),Pi=N (wP ,σ2wIdw ) er(Ab(Si, Pi))
+ 1
(1− e−c1)n
( 1
2σ2v ‖vQ‖2 + log 1 δ0
) ,∀Q } ≥ 1− δ0, (38)
Finally, by employing the union bound, we could bound the probability of the intersection of the events in (36) and (38) For any δ > 0, set δ0 , δ2 and δi , δ 2n for i = 1, . . . , n, we have
P(Dmii )∼τ,Si∼Dmii ,i=1,...,n
{ er(Q)
≤ c1c2 (1− e−c1)(1− e−c2) · 1 n n∑ i=1 E v∼N (vQ,σ2vIdv ),wP =Φv(D),Pi=N (wP ,σ2wIdw ) êr(Ab(Si, Pi))
+ c1 1− e−c1 · 1 n n∑ i=1
1
(1− e−c2)mi
( 1
2σ2v ‖vQ‖2 + 1 σ2w ‖E v wQi − Φ̄vQ(Si)‖ 2 + log 4n δ
+ 1
σ2w K∑ k=1 ( αR √ mik (1 + √ 1 2 log( 4n δ )) +Oα,β(γ,C) )2 + dwK( σv σw )2  + 1
(1− e−c1)n
( 1
2σ2v ‖vQ‖2 + log 2 δ
) ,∀Q } ≥ 1− δ. (39)
We can further simplify the notation and obtain that
P(Dmii )∼τ,Si∼Dmii ,i=1,...,n
{ er(Q) ≤ c′1c′2êr(Q)
+( n∑ i=1
c′1c ′ 2
2c2nmiσ2v + c′1 2c1nσ2v )‖vQ‖2 + n∑ i=1 c′1c ′ 2 c2nmiσ2w ‖E v wQi − Φ̄vQ(Si)‖ 2
+const(α, β,R, δ, n,mi),∀Q } ≥ 1− δ, (40)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 . This completes the proof.462
B.4 PROOF OF THEOREM 2463
Theorem 2 Let Q be the posterior of base learner Q = N (wQ, σ2wIdw) and P be the prior N (wP , σ2wIdw). The mean of prior is sampled from the hyperposterior of meta learner Q = N (wQ, σ2wIdw). Give the hyperprior P = N (0, σ2wIdw), then for any hyperposterior Q, any
c1, c2 > 0 and any δ ∈ (0, 1] with probability ≥ 1− δ we have,
er(Q) ≤c′1c′2êr(Q) + ( n∑ i=1
c′1c ′ 2
2c2nmiσ2w + c′1 2c1nσ2w )‖wQ‖2 + n∑ i=1
c′1c ′ 2
2c2nmiσ2w ‖ E wP wQi −w Q‖2
+ n∑ i=1 c′1c ′ 2 c2nmiσ2w ( 1 2 + log 2n δ ) + c′1 c1nσ2w log 2 δ , (41)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 .464
Proof Instead of generating the mean of prior with a prior predictor, the vanilla meta-learning framework directly produces the mean of prior wP by sampling from hyperposterior Q = N (wQ, σ2wIdw). Then the base learner algorithm Ab(S, P ) utilizes the sample set S and the prior P = N (wP , σ2wIdw) to produce a posterior Q = Ab(S, P ) = N (wQ, σ2wIdw). 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
PSi∼Dmii
{ E
(x,y)∼Di E wP∼N (wQ,σ2wIdw ) E w∼N (wQ,σ2wIdw ) `(hw(x), y)
≤ c2 1− e−c2 · 1 mi mi∑ j=1 E wP∼N (wQ,σ2wIdw ) E w∼N (wQ,σ2wIdw ) `(hw(xj), yj)
+ 1
(1− e−c2) ·mi
( 1
2σ2w ‖wQ‖2 + E wPi ∼N (wQ,σ2wIdw )
1
2σ2w ‖wQi −w P i ‖2 + log
1
δi
) ,∀Q } ≥ 1− δi,
(42)
The term E wPi ∼N (wQ,σ2wIdw ) 1 2σ2w ‖wQi −wPi ‖2 can be simplified as
E wPi ∼N (wQ,σ2wIdw )
1
2σ2w ‖wQi −w P i ‖2
= 1
2σ2w
( E wP ‖wQi ‖ 2 − 2( E wP wQi ) >wQ + ‖wQ‖2 + V
wPi
[‖wPi ‖] )
= 1
2σ2w
( ‖ E wP wQi −w Q‖2 + σ2w ) , (43)
where V wPi [‖wPi ‖] denotes the variance of ‖wPi ‖. Then we get an inter-task bound. For any δ0 > 0, we have
P(Dmii )∼τ,Si∼Dmii ,i=1,...,n
{ E
(D,m)∼τ E S∼Dm E wP∼N (wQ,σ2wIdw ) E w∼N (wQ,σ2wIdw ) E (x,y)∼Di `(hw(x), y)
≤ c1 1− e−c1 · 1 n n∑ i=1 E wP∼N (wQ,σ2wIdw ) E w∼N (wQ,σ2wIdw ) E (x,y)∼Di `(hw(x), y)
+ 1
(1− e−c1)n
( 1
2σ2w ‖wQ‖2 + log 1 δ0
) ,∀Q } ≥ 1− δ0. (44)
For any δ > 0, set δ0 , δ2 and δi , δ 2n for i = 1, . . . , n. Using the union bound, we finally get
P(Dmii )∼τ,Si∼Dmii ,i=1,...,n
{ er(Q)
≤ c1c2 (1− e−c1)(1− e−c2) · 1 n n∑ i=1 E v∼N (vQ,σ2vIdv ),wP =Φv(D),Pi=N (wP ,σ2wIdw ) êr(Ab(Si, Pi))
+ c1 1− e−c1 · 1 n n∑ i=1
1
(1− e−c2) ·mi
( 1
2σ2w ‖wQ‖2 + 1 2σ2w ‖ E wP wQi −w Q‖2 + 1 2 + log 2n δ
)
+ 1
(1− e−c1)n
( 1
2σ2w ‖wQ‖2 + log 2 δ
) ,∀Q } ≥ 1− δ. (45)
Similarly, we can further simplify the notation and obtain that
P(Dmii )∼τ,Si∼Dmii ,i=1,...,n
{ er(Q) ≤ c′1c′2êr(Q)
+( n∑ i=1
c′1c ′ 2
2c2nmiσ2w + c′1 2c1nσ2w )‖wQ‖2 + n∑ i=1
c′1c ′ 2
2c2nmiσ2w ‖ E wP wQi −w Q‖2
+const(δ, n,mi),∀Q } ≥ 1− δ, (46)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 . This completes the proof.465
C DETAILS OF EXPERIMENTS466
C.1 DATA PREPARATION467
We used the 5-way 50-shot classification setups, where each task instance involves classifying im-468 ages from 5 different categories sampled randomly from one of the meta-sets. We did not employ469 any data augmentation or feature averaging during meta-training, or any other data apart from the470 corresponding training and validation meta-sets.471
C.2 NETWORK ARCHITECHTURE472
Auto-Encoder for LCC For CIFAR100, the encoder is 7 layers with 16-32-64-64-128-128-256473 channels. Each convolutional layer is followed by a LeakyReLU activation and a batch normaliza-474 tion layer. The 1st, 3rd and 5th layer have stride 1 and kernel size (3, 3). The 2nd, 4th and 6th layer475 have stride 2 and kernel size (4, 4). The 7th layer has stride 1 and kernel size (4, 4). The decoder is476 the same as encoder except that the layers are in reverse order. The input is resized to 32× 32. For477 Caltech-256, the encoder is 5 layers with 32-64-128-256-256 channels. Each convolutional layer is478 followed by a LeakyReLU activation and a batch normalization layer. The first 4 layers have stride479 2 and kernel size (4, 4). The last layer has stride 1 and kernel size (6, 6). The decoder is the same480 as encoder except that the layers are in reverse order. The input is resized to 96× 96.481 Base Model The network architecture used for the classification task is a small CNN with 4 con-482 volutional layers, each with 32 filters, and a linear output layer, similar to (Finn et al., 2017). Each483 convolutional layer is followed by a Batch Normalization layer, a Leaky ReLU layer, and a max-484 pooling layer. For CIFAR100, the input is resized to 32 × 32. For Caltech-256, the input is resized485 to 96× 96.486
C.3 OPTIMIZATION487
Auto-Encoder for LCC As optimizer we used Adam(Kingma & Ba, 2015) with β1 = 0.9 and488 β2 = 0.999. The initial learning rate is 1 × 10−4. The number of epochs is 100. The batch size is489 512.490
LCC Training We alternatively train the coefficients and bases of LCC with Adam with β1 = 0.9491 and β2 = 0.999. In specifics, for both datasets, we alternatively update the coefficients for 60 times492 and then update the bases for 60 times. The number of training epochs is 3.The number of bases is493 64. The batch size is 256.494
Pre-Training of Feature Extractor We use a 64-way classification in CIFAR-100 and 150-way495 classification in Caltech-256 to pre-train the feature embedding only on the meta-training dataset.496 For both CIFAR100 and Caltech-256, an L2 regularization term of 5e−4 was used. We used the497 Adam optimizer. The initial learning rate is 1 × 10−3, β1 is 0.9 and β2 is 0.999. The number of498 epochs is 50. The batch size is 512.499
Meta-Training We use the cross-entropy loss as in (Amit & Meir, 2018). Although this is inconsis-500 tent with the bounded loss setting in our theoretical framework, we can still have a guarantee on a501 variation of the loss which is clipped to [0, 1]. In practice, the loss is almost always smaller than one.502 For CIFAR100 and Caltech-256, the number of epochs of meta-training phase is 12; the number of503 epochs of meta-testing phase is 40. The batch size is 32 for both datasets. As optimizer we used504 Adam with β1 = 0.9 and β2 = 0.999. In the setting with a pre-trained base model, the learning rate505 is 1× 10−5 for convolutional layers and 5× 10−4 for the linear output layer. In the setting without506 a pre-trained base model, the learning rate is 1× 10−3 for convolutional layers and 5× 10−3 for the507 linear output layer. The confidence parameter is chosen to be δ = 0.1. The variance hyper-parameter508 for prior predictor and base model are σw = σv = 0.01. The hyperparameter α1, α2 in LML and509 ML-A are set to 0.01. For MAML (Finn et al., 2017) and MatchingNet (Vinyals et al., 2016). Both510 two methods use the Adam optimizer with initial learning rate 0.0001. In the meta-training phase,511 we randomly split the samples of each class into support set (5 samples) and query set (45 samples).512 The number of epochs is 100. For MAML, the learning rate of inner update is 0.01.513

Review summaries:
This paper discusses a theoretical analysis of localized meta-learning. The authors are motivated from a PAC-Bayes perspective of meta-learning wherein the system learns a hyper-prior on the hypothesis space using the posteriors of the weak-learners learnt on their individual tasks. The first contribution of the paper is to construct a PAC-Bayes generalization bound for the case when the hyper-prior and the prior on the new task are both isotropic Gaussian. The second contribution is to develop a localized meta-learning algorithm which predicts a better prior for the weak-learner using the data distribution of the new task. The authors use ideas from metric learning to learn the predictor for the prior using Local Coordinate Coding.