Year: 2020

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 Such meta-knowledge is often represented as a fixed distribution; this, however, 3 may be too restrictive to capture various specific task information because the 4 discriminative patterns in the data may change dramatically across tasks. In this 5 work, we aim to equip the meta learner with the ability to model and produce 6 task-specific meta knowledge and, accordingly, present a localized meta-learning 7 framework based on the PAC-Bayes theory. In particular, we propose a Local 8 Coordinate Coding (LCC) based prior predictor that allows the meta learner to 9 generate local meta-knowledge for specific tasks adaptively. We further develop a 10 practical algorithm with deep neural network based on the bound. Empirical results 11 on real-world datasets demonstrate the efficacy of the proposed method. 12

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 Such meta-knowledge is often represented as a fixed distribution; this, however,3 may be too restrictive to capture various specific task information because the4 discriminative patterns in the data may change dramatically across tasks. In this5 work, we aim to equip the meta learner with the ability to model and produce6 task-specific meta knowledge and, accordingly, present a localized meta-learning7 framework based on the PAC-Bayes theory. In particular, we propose a Local8 Coordinate Coding (LCC) based prior predictor that allows the meta learner to9 generate local meta-knowledge for specific tasks adaptively. We further develop a10 practical algorithm with deep neural network based on the bound. Empirical results11 on real-world datasets demonstrate the efficacy of the proposed method.12
1 INTRODUCTION13
Task 1 Instances
Task 2 Instances
Global Meta-knowledge Localized Meta-knowledge
Adaptation
Recent years have seen a resurgence of interest in the14 field of meta-learning, or learning-to-learn (Thrun15 & Pratt, 2012), especially for empowering deep neu-16 ral networks with the capability of fast adapting to17 unseen tasks just as humans (Finn et al., 2017; Ravi18 & Larochelle, 2017). More concretely, the neural19 networks are trained from a sequence of datasets,20 associated with different tasks sampled from a meta-21 distribution (also called task environment (Baxter,22 2000; Maurer, 2005)). The principal aim of meta23 learner is to extract transferable meta-knowledge24 from observed tasks and facilitate the learning of25 new tasks sampled from the same meta-distribution.26 The performance is measured by the generalization27
tasks: distinguishing motorcycle versus bicycle and distinguishing motorcycle versus car. Intuitively,45 each task uses distinct discriminative patterns and thus the desired meta-knowledge is required46 to extract these patterns simultaneously. It could be a challenging problem to represent it with a47 global hyperposterior since the most significant patterns in the first task could be irrelevant or even48 detrimental to the second task. Figure schematically illustrates this notion. Therefore, customized49 meta-knowledge such that the patterns are most discriminative for a given task is urgently desired.50 Can the meta-knowledge be adaptive to tasks? How can one achieve it? Intuitively, we could51 implement this idea by reformulating the meta-knowledge as a maping function. Leveraging the52 samples in the target task, the meta model produces tasks specific meta-knowledge.53
Naturally yet interestingly, one can see quantitatively how customized prior knowledge improves54 generalization capability, in light of the PAC-Bayes literature on the data distribution dependent-priors55 (Catoni, 2007; Parrado-Hernández et al., 2012; Dziugaite & Roy, 2018). Specifically, PAC-Bayes56 bounds control the generalization error of Gibbs Classifiers. They usually depend on a tradeoff57 between the empirical error of the posterior Q and a KL-divergence term KL(Q‖P ), where P is the58 prior. Since this KL-divergence term forms part of the generalization bound and is typically large in59 standard PAC-Bayes approaches (Lever et al., 2013), the choice of posterior is constrained by the60 need to minimize the KL-divergence between prior P and posterior Q. Thus, choosing an appropriate61 prior for each task which is close to the related posterior could yield improved generalization bounds.62 This encourages the study of data distribution-dependent priors for the PAC-Bayes analysis and gives63 rise to principled approaches to localized PAC-Bayes analysis. Previous related work are mainly64 discussed in Appendix A.65
Inspired by this, we propose a Localized Meta-Learning (LML) framework by formulating meta-66 knowledge as a conditional distribution over priors. Given task data distribution, we allow a meta67 learner to adaptively generate an appropriate prior for a new task. The challenges of developing this68 model are three-fold. First, the task data distribution is not explicitly given, and our only perception69 for it is via the associated sample set. Second, it should be permutation invariant — the output of70 model should not change under any permutation of the elements in the sample set. Third, the learned71 model could be used for solving unseen tasks. To address these problems, we further develop a prior72 predictor using Local Coordinate Coding (LCC)(Yu et al., 2009). In particular, if the classifier in73 each task is specialized to a parametric model, e.g. deep neural network, the proposed LCC-based74 prior predictor predicts base model parameters using the task sample set. The main contributions75 include: (1) A localized meta-learning framework which provides a means to tighten the original76 PAC-Bayes meta-learning bound (Pentina & Lampert, 2014; Amit & Meir, 2018) by minimizing77 the task-complexity term by choosing data-dependent prior; (2) An LCC-based prior predictor, an78 implementation of conditional hyperposterior, which generates local meta-knowledge for specific79 task; (3) A practical algorithm for probabilistic deep neural networks by minimizing the bound80 (though the optimization method can be applied to a large family of differentiable models); (4)81 Experimental results which demonstrate improved performance over meta-learning method in this82 field.83
2 PRELIMINARIES84
Our prior predictor was implemented by Local Coordinate Coding (LCC). The LML framework85 was inspired by PAC-Bayes theory for meta learning. In this section we briefly review the related86 definitions and formulations.87
2.1 LOCAL COORDINATE CODING88
Definition 1. (Lipschitz Smoothness Yu et al. (2009).) A function f(x) in Rd is a (α, β)-Lipschitz89 smooth w.r.t. a norm ‖ · ‖ if ‖f(x)−f(x′)‖ ≤ α‖x−x′‖ and ‖f(x′)−f(x)−∇f(x)>(x′−x)‖ ≤90 β‖x− x′‖2.91 Definition 2. (Coordinate Coding Yu et al. (2009).) A coordinate coding is a pair (γ, C), where92 C ⊂ Rd is a set of anchor points(bases), and γ is a map of x ∈ Rd to [γu(x)]u∈C ∈ R|C| such that93 ∑
u γu(x) = 1. It induces the following physical approximation of x in Rd : x̄ = ∑ u∈C γu(x)u.94
Definition 3. (Latent Manifold Yu et al. (2009).) A subsetM ⊂ Rd is called a smooth manifold with an intrinsic dimension |C| := dM if there exists a constant cM such that given any x ∈ M,
there exists |C| anchor points u1(x), . . . ,u|C|(x) ∈ Rd so that ∀x′ ∈M:
inf γ∈R|C| ‖x′ − x− |C|∑ j=1 γjuj(x)‖2 ≤ cM‖x′ − x‖22,
where γ = [γ1, . . . , γ|C|]> are the local codings w.r.t. the anchor points.b95
Definition 2 and 3 imply that any point in Rd can be expressed as a linear combination of a set96 of anchor points. Later, we will show that a high dimensional nonlinear prior predictor can be97 approximated by a simple linear function w.r.t. the coordinate coding, and the approximation quality98 is ensured by the locality of such coding (each data point can be well approximated by a linear99 combination of its nearby anchor points).100
2.2 PAC-BAYES REGULAR META-LEARNING101
In order to present the advances proposed in this paper, we recall some definitions in PAC-Bayes102 theory for single-task learning and meta-learning (Catoni, 2007; Baxter, 2000; Pentina & Lampert,103 2014; Amit & Meir, 2018). In the context of classification, we assume all tasks share the same input104 space X , output space Y , space of classifiers (hypotheses) H ⊂ {h : X → Y} and loss function105 ` : Y × Y → [0, 1]. The meta learner observes n tasks in the form of sample sets S1, . . . , Sn. The106 number of samples in task i is denoted by mi. Each observed task i consists of a set of i.i.d. samples107 Si = {(xj , yj)}mij=1, which is drawn from a data distribution Si ∼ D mi i . Following the meta-learning108 setup in (Baxter, 2000), we assume that each data distribution Di is generated i.i.d. from the same109 meta distribution τ . Let h(x) be the prediction of x, the goal of each task is to find a classifier h110 that minimizes the expected loss Ex∼D`(h(x), y). Since the underlying ‘true’ data distribution Di is111 unknown, the base learner receives a finite set of samples Si and produces an “optimal” classifier112 h = Ab(Si) with a learning algorithm Ab(·) that will be used to predict the labels of unseen inputs.113 PAC-Bayes theory studies the properties of randomized classifier, called Gibbs classifier. Let Q be a114 posterior distribution overH. To make a prediction, the Gibbs classifier samples a classifier h ∈ H115 according to Q and then predicts a label with the chosen h. The expected error under data distribution116 D and empirical error on the sample set S are then given by averaging over distribution Q, namely117 er(Q) = Eh∼QE(x,y)∼D`(h(x), y) and êr(Q) = Eh∼Q 1m ∑m j=1 `(h(xj), yj), respectively.118
In the context of meta-learning, 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. In each task, the prior knowledge P is in the form of a distribution over classifiersH. 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 meta-knowledge 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. Given this, 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: er(Q) = EP∼QE(D,m)∼τ,S∼Dmer(Q = Ab(S, P )). (1) 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 )). (2)
2.3 PAC-BAYES REGULAR META-LEARNING BOUND WITH GAUSSIAN RANDOMIZATION119
Based on the above definitions, Pentina & Lampert (2014) and Amit & Meir (2018) present regular120 meta-learning PAC-Bayes generalization bounds w.r.t. hyperposteriorQ. Notably, the proof technique121 in Amit & Meir (2018) allows to incorporate different single task bounds. Consider the benefit of122 Catoni’s bound (Catoni, 2007) (the minimization problem derived from the bound is a simple linear123 combination of empirical risk plus a regularizer), here we instantiate a regular meta-learning bound124 with Gaussian randomization based on that. To make fair comparison, we will adopt the same Catoni’s125 bound to analysis the proposed LML framework later. Particularly, the classifier h is parameterized126 as hw with w ∈ Rdw . The prior and posterior are a distribution over the set of all possible parameters127 w. We choose both the prior P and posterior Q to be spherical Gaussians, i.e. P = N (wP , σ2wIdw)128
and Q = N (wQ, σ2wIdw). The mean wP is a random variable distributed first according to the129 hyperprior P , which we formulate as N (0, σ2wIdw), and later according to hyperposterior Q, which130 we model as N (wQ, σ2wIdw). When encountering a new task i, we first sample the mean of prior131 wPi from the hyperposterior N (wQ, σ2wIdw), and then use it as a basis to learn the mean of posterior132 wQi = Ab(Si, P ), as shown in Figure 2(left). Then, we could derive the following PAC-Bayes133 meta-learning bound.134
Theorem 1. Consider the regular meta-learning framework, given the hyperpriorP = 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 δ , (3)
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σ2w + c′1 2c1nσ2w )‖wQ‖2 + n∑ i=1
c′1c ′ 2
2c2nmiσ2w ‖ E wP wQi −w Q‖2︸ ︷︷ ︸
task−complexity
+ const(δ, n,mi, σw, c1, c2). (4)
See Appendix D.4 for the proof. Notice that the expected task generalization error is bounded by the135 empirical multi-task error plus two complexity terms which measures the environment-complexity136 and the task-complexity, respectively.137
3 PAC-BAYES LOCALIZED META-LEARNING138 3.1 MOTIVATION AND OVERALL FRAMEWORK139 Our motivation stems from a core challenge in PAC-Bayes meta-learning bound in (4), wherein140 the task-complexity term ∑n i=1 c′1c ′ 2 2c2nmiσ2w ‖EwQi −wQ‖2, which measures the closeness between141 the mean of posterior and the mean of global hyperposterior for each task, is typically vital to the142 generalization bound. Finding the tightest possible bound generally depends on minimizing this143
term. It is obvious that the optimal wQ is ∑n i=1 c′1c ′ 2Ew Q i
2c2nmiσ2w . This solution for global hyperposterior is144 required to satisfy the task similarity assumption that the optimal posteriors for each task are close145 together and lie within a small subset of the model space. Under this circumstance, there exists a146 global hyperposterior from which a good prior for any individual task is reachable. However, if the147 optimal posteriors for each task are not related or even mutually exclusive, i.e., one optimal posterior148 has a negative effect on another task, the global hyperposterior may impede the learning of some149 tasks. Moreover, this complexity term could be inevitably large and incur large generalization error.150
Note that wQ is the mean of hyperposterior Q and this complexity term naturally indicates the151 divergence between the mean of prior wPi sampled from the hyperposterior Q and the mean of152 posterior wQi in each task. Therefore, we propose to adaptively choose the mean of prior w P i153
according to task i. It is obvious that the complexity term vanishes if we set wPi = w Q i , but the prior154 Pi in each task has to be chosen independently of the sample set Si. Fortunately, the PAC-Bayes155
theorem allows us to choose prior upon the data distribution Di. Therefore, we propose a prior156 predictor Φ : Dm → wP which receives task data distribution Dm and outputs the mean of prior157 wP . In this way, the generated priors could focus locally on those regions of model parameters that158 are of particular interest in solving specific tasks.159
Particularly, the prior predictor is parameterized as Φv with v ∈ Rdv . We assume v to be a random160 variable distributed first according to the hyperprior P , which we reformulate as N (0, σ2vIdv), and161 later according to hyperposteriorQ, which we reformulate asN (vQ, σ2vIdv). Given a new task i, we162 first sample v from hyperposterior N (vQ, σ2vIdv) and estimate the mean of prior wPi by leveraging163 prior predictor wPi = Φv(D m i ). Then, the base learner utilizes the sample set Si and the prior164
Pi = N (wPi , σ2wIdw) to produce a mean posterior w Q i = Ab(Si, Pi), as shown in Figure 2(right).165
To make wP close to wQ in each task, what properties are the prior predictor is expected to exhibit?166 Importantly, it is required to (i) uncover the tight relationship between the sample set and model167 parameters. Intuitively, features and parameters yield similar local and global structures in their168 respective spaces in the classification problem. Features in the same category tend to be spatially169 clustered together while maintaining the separation between different classes. Take linear classifiers170 as an example, let wk be the parameters w.r.t. category k, the separability between classes is171 implemented as x · wk, which also explicitly encourages intra-class compactness. A reasonable172 choice of wk is to maximize the inner product distance with the input features in the same category173 and minimize the distance with the input features of the non-belonging categories. Besides, the prior174 predictor should be (ii) category-agnostic since it will be used continuously as new tasks and hence175 new categories become available. Lastly, it should be (iii) invariant under permutations of its inputs.176
3.2 LCC-BASED PRIOR PREDICTOR177
There exists many implementations, such as set transformer (Lee et al., 2018), relation network (Rusu178 et al., 2019), task2vec(Achille et al., 2019), that satisfy the above conditions. We follow the idea of179 nearest class mean classifier (Mensink et al., 2013), which represents class parameter by averaging180 its feature embeddings. This idea has been explored in transductive few-shot learning problems (Snell181 et al., 2017; Qiao et al., 2018). Snell et al. (2017) learn a metric space across tasks such that when182 represented in this embedding, prototype (centroid) of each class can be used for label prediction183 in the new task. Qiao et al. (2018) directly predict the classifier weights using the activations by184 exploiting the close relationship between the parameters and the activations in a neural network185 associated with the same category. In summary, the classification problem of each task is transformed186 as a generic metric learning problem which is shared across tasks. Once this mapping has been187 learned on observed tasks, due to the structure-preserving property, it could be easily generalized to188 new tasks. Formally, consider each task as a K-class classification problem, and the parameter of the189 classifier in task i denoted as wi = [wi[1], . . . ,wi[k], . . . ,wi[K]], the prior predictor for class k can190 be defined as:191
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. Note that if the prior predictor is relatively stable to perturbations of the sample set, then the generated prior could still reflect the underlying task data distribution, rather than the data, resulting in a generalization bound that still holds perhaps with smaller probability (Dziugaite & Roy, 2018). Formally, the empirical prior predictor is defined as:
ŵPi [k] = Φ̂v(Sik) = 1
mik ∑ xj∈Sik φv(xj). (6)
Although we can implement the embedding function φv(·) with a multilayer perceptron (MLP), both input x ∈ Rd and model parameter w ∈ Rdw are high-dimensional, making the empirical prior predictor Φ̂v(·) difficult to learn. Inspired by the local coordinate coding method, if the anchor points are sufficiently localized, the embedding function φv(xj) can be approximated by a linear function w.r.t. a set of codings, [γu(xj)]u∈C . Accordingly, we propose an LCC-based prior predictor, which
is defined as: w̄Pi [k] = Φ̄v(Sik) = 1
mik ∑ xj∈Sik ∑ u∈C γu(xj)φv(u), (7)
where φv(u) ∈ Rdw is the embedding of the corresponding anchor point u ∈ C. As such,192 the parameters of LCC-based prior predictor w.r.t. category k can be represented as vk =193 [φvk(u1), φvk(u2), . . . , φvk(u|C|)]. Lemma 1 illustrates the approximation error between empirical194 prior predictor and LCC-based prior predictor.195 Lemma 1. (Empirical Prior 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 φv(·) be an (α, β)-Lipschitz smooth function. We have for all x ∈ Rd
‖ŵPi [k]− w̄Pi [k]‖ ≤ Oα,β(γ,C) (8) whereOα,β(γ,C) = 1mik ∑ xj∈Sik ( α‖xj− x̄j‖+β ∑ u∈C ‖x̄j−u‖2 ) and x̄j = ∑ u∈C γu(xj)u.196
See Appendix D.1 for the proof. Lemma 1 shows that a good LCC-based prior predictor should make197 x close to its physical approximation x̄ and should be localized. The complexity of LCC coding198 scheme depends on the number of anchor points |C|. We follow the optimization method in Yu et al.199 (2009) to find the coordinate coding (γ,C), which is presented in Appendix B.200
3.3 PAC-BAYES LOCALIZED META-LEARNING BOUND WITH GAUSSIAN RANDOMIZATION201
In order to derive a PAC-Bayes generalization bound for localized meta-learning, we first bound the202 approximation error between expected prior predictor and LCC-based prior predictor.203 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 .
See Appendix D.2 for the proof. Lemma 2 shows that the approximation error between expected204 prior predictor and LCC-based prior predictor depends on (i) the concentration of prior predictor205 and (ii) the quality of LCC coding scheme. The first term implies the number of samples for each206 category should be larger for better approximation. This is consistent with the results of estimating207 the center of mass (Cristianini & Shawe-Taylor, 2004). Based on Lemma 2, using the same Catoni’s208 bound. we have the following PAC-Bayes LML bound.209 Theorem 2. Consider the localized meta-learning 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σ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 δ , (9)
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︸ ︷︷ ︸ task−complexity
+ const(α, β,R, δ, n,mi, σv, σw, c1, c2). (10)
See appendix D.3 for the proof. Similarly to the regular meta-learning bound in Theorem 1, the210 expected task error er(Q) is bounded by the empirical task error êr(Q) plus the task-complexity and211 environment-complexity terms. The main innovation here is to exploit the potential to choose the212 mean of prior wP adaptively, based on task data S. Intuitively, if the selection of the LCC-based213 prior predictor is appropriate, it will narrow the divergence between the mean of prior wPi sampled214
from the hyperposterior Q and the mean of posterior wQi in each task. Therefore, the bound can be215 tighter than the ones in the regular meta-learning (Pentina & Lampert, 2014; Amit & Meir, 2018).216 Our empirical study in Section 4 will illustrate that the algorithm derived from this bound can217 reduce task-complexity and thus achieve better performance than the methods derived from regular218 meta-learning bounds.219
When one is choosing the number of anchor points |C|, there is a balance between accuracy and220 simplicity of prior predictor. As we increase |C|, it will essentially increase the expressive power of221 Φ̄v(·) and reduce the task-complexity term ‖E
v wQ − Φ̄vQ(S)‖2. However, at the same time, it will222 increase the enviornment-complexity term ‖vQ‖2 and make the bound loose. If we set |C| to 1, it223 degenerates to the regular meta-learning framework.224
3.4 LOCALIZED META-LEARNING ALGORITHM225
Since the bound in (9) holds uniformly w.r.t. Q, the guarantees of Theorem 2 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 (9) can be compactly written as ∑n i=1 Ev êri(Qi = Ab(Si, P )) +α1‖v Q‖2 + ∑n i=1 α2 mi ‖E v wQi − Φ̄vQ(Si)‖2, 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)). To make fair comparison and guarantee the benefit of
the proposed LML is not from using an improved optimization method, we follow the same learning algorithm in (Amit & Meir, 2018). Specifically, we jointly optimize 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. (11)
We can optimize v and w via mini-batch SGD. The details of the localized meta-learning algorithm226 is given in Appendix F. The expectation over Gaussian distribution and its gradient can be efficiently227 estimated by using the re-parameterization trick Kingma & Welling (2014); Rezende et al. (2014).228 For example, to sample w from the posterior Q = N (wQ, σ2wIdw), we first draw ξ ∼ N (0, Idw)229 and then apply the deterministic function wQ + ξ σ, where is an element-wise multiplication.230
4 EXPERIMENTS231
Datasets and Setup. We use CIFAR-100 and Caltech-256 in our experiments. CIFAR-100232 Krizhevsky (2009) contains 60,000 images from 100 fine-grained categories and 20 coarse-level233 categories. As in Zhou et al. (2018), we use 64, 16, and 20 classes for meta-training, meta-validation,234 and meta-testing, respectively. Caltech-256 has 30,607 color images from 256 classes Griffin et al.235 (2007). Similarly, we split the dataset into 150, 56 and 50 classes for meta-training, meta-validation,236 and meta-testing. We consider 5-way classification problem. Each task is generated by randomly237 sampling 5 categories and each category contains 50 samples. The base model uses the convolutional238 architecture in Finn et al. (2017), which consists of 4 convolutional layers, each with 32 filters and a239 fully-connected layer mapping to the number of classes on top. High dimensional data often lies on240 some low dimensional manifolds. We utilize an auto-encoder to extract the semantic information of241 image data and then construct the LCC scheme based on the embeddings. The parameters of prior242 predictor and base model are random perturbations in the form of Gaussian distribution.243
We design two different meta-learning environment settings to validate the efficacy of the proposed244 method. The first one uses the pre-trained base model as an initialization, which utilizes all the245 meta-training classes (64-class classification in CIFAR-100 case) to train the feature extractor. The246 second one uses the random initialization. We compare the proposed LML method with ML-PL247 method Pentina & Lampert (2014), ML-AM method Amit & Meir (2018) and ML-A which is248 derived from Theorem 1. In all these methods, we use their main theorems about the generalization249 upper bound to derive the objective of the algorithm. To ensure a fair comparison, all approaches250 adopt the same network architecture and pre-trained feature extractor (more details can be found in251 Appendix E).252
Results. In Figure 3, we demonstrate the average test error of learning a new task based on the253 number of training tasks, together with the standard deviation, in different settings (with or without254 a pre-trained feature extractor). It is obvious that the performance continually increases as we255 increase the number of training tasks for all the methods. This is consistent with the generalization256 bounds that the complexity term converges to zero if large numbers of tasks are observed. ML-A257 consistently outperforms ML-PL and ML-AM since the single-task bound used in Theorem 1(ML-A)258 converges at the rate of O( 1m ) while the bounds w.r.t. ML-PL and ML-AM converge at the rate259 of O( 1√
m ). This demonstrates the importance of using tight generalization bound. Moreover, our260 proposed LML significantly outperforms the baselines, which validates the effectiveness of the261 proposed LCC-based prior predictor. This confirms that LCC-based prior predictor is a more suitable262 representation for meta-knowledge than the traditional global hyperposterior in ML-A, ML-AM,263 and ML-PL. Finally, we observe that if the pre-trained feature extractor is provided, all of these264 methods do better than meta-training with random initialization. This is because the pre-trained265 feature extractor can be regarded as a data-dependent hyperpior. It is closer to the hyperposteior than266 the randomly initialized hyperprior. Therefore, it is able to reduce the environment complexity term267 and improves the generalization performance.
In Figure 4(b), we show the divergence between the mean of generated prior wP from meta model269 and the mean of learned posterior wQ for LML and ML-A. This further validates the effectiveness of270 the LCC-based prior predictor which could narrow down the divergence term and thus tighten the271 bound. In Figure 4(a), we vary the number of anchor points |C| in LCC scheme from 4 to 256, the272 optimal value is around 64 in both datasets. This indicates that LML is sensitive to the number of273 anchor points |C|, which further affects the quality of LCC-based prior predictor and the performance274 of LML.275
5 CONCLUSION276 This work contributes a novel localized meta-learning framework from both the theoretical and277 computational perspectives. In order to tailor meta-knowledge to various individual task, we formulate278 meta model as a mapping function that leverages the samples in target set and produces task specific279 meta-knowledge as a prior. Quantitatively, this idea essentially provides a means to theoretically280 tighten the PAC-Bayes meta-learning generalization bound. We propose a LCC-based prior predictor281 to output localized meta-knowledge by using task information and further develop a practical282 algorithm with deep neural networks by minimizing the generalization bound. An interesting283 topic for future work would be to explore other principles to construct the prior predictor and apply284 the localized meta-learning framework to more realistic scenarios where tasks are sampled non-i.i.d.285 from an environment. Another challenging problem is to extend our techniques to derive localized286 meta-learning algorithms for regression and reinforcement learning problems.287
REFERENCES288 Alessandro Achille, Michael Lam, Rahul Tewari, Avinash Ravichandran, Subhransu Maji, Charless C289 Fowlkes, Stefano Soatto, and Pietro Perona. Task2vec: Task embedding for meta-learning. In290 Proceedings of the IEEE International Conference on Computer Vision, pp. 6430–6439, 2019.291
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-Bayes theory. In292 International Conference on Machine Learning, pp. 205–214, 2018.293
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient-based294 meta-learning. In Proceedings of the 36th International Conference on Machine Learning, ICML295 2019, 9-15 June 2019, Long Beach, California, USA, pp. 424–433, 2019.296
Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12:297 149–198, 2000.298
O Catoni. PAC-Bayesian supervised classification: The thermodynamics of statistical learning.299 institute of mathematical statistics lecture notes—monograph series 56. IMS, Beachwood, OH.300 MR2483528, 2007.301
Nello Cristianini and John Shawe-Taylor. Kernel methods for pattern analysis, volume 173. Cam-302 bridge University Press Cambridge, 2004.303
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to-304 learn with statistical guarantees. In Proceedings of the Thirty-Fourth Conference on Uncertainty305 in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pp. 457–466,306 2018a.307
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around a308 common mean. In Advances in Neural Information Processing Systems, pp. 10169–10179, 2018b.309
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-learn stochas-310 tic gradient descent with biased regularization. In Proceedings of the 36th International Conference311 on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 1566–1575,312 2019.313
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent PAC-Bayes priors via differential314 privacy. In Advances in Neural Information Processing Systems, pp. 8430–8441, 2018.315
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of316 deep networks. In Proceedings of the 34th International Conference on Machine Learning-Volume317 70, pp. 1126–1135. JMLR. org, 2017.318
Tomer Galanti, Lior Wolf, and Tamir Hazan. A theoretical framework for deep transfer learning.319 Information and Inference: A Journal of the IMA, 5(2):159–209, 2016.320
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.321
Benjamin Guedj. A primer on pac-bayesian learning. arXiv preprint arXiv:1901.05353, 2019.322
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International323 Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015,324 Conference Track Proceedings, 2015.325
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International326 Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014,327 Conference Track Proceedings, 2014.328
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer,329 2009.330
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R Kosiorek, Seungjin Choi, and Yee Whye Teh. Set331 transformer: A framework for attention-based permutation-invariant neural networks. arXiv332 preprint arXiv:1810.00825, 2018.333
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter PAC-Bayes bounds through334 distribution-dependent priors. Theoretical Computer Science, 473:4–28, 2013.335
Andreas Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research, 6336 (Jun):967–994, 2005.337
Thomas Mensink, Jakob Verbeek, Florent Perronnin, and Gabriela Csurka. Distance-based image338 classification: Generalizing to new classes at near-zero cost. IEEE transactions on pattern analysis339 and machine intelligence, 35(11):2624–2637, 2013.340
Emilio Parrado-Hernández, Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC-Bayes341 bounds with data dependent priors. Journal of Machine Learning Research, 13(Dec):3507–3531,342 2012.343
Anastasia Pentina and Christoph Lampert. A PAC-Bayesian bound for lifelong learning. In Interna-344 tional Conference on Machine Learning, pp. 991–999, 2014.345
Siyuan Qiao, Chenxi Liu, Wei Shen, and Alan L. Yuille. Few-shot image recognition by predicting pa-346 rameters from activations. In 2018 IEEE Conference on Computer Vision and Pattern Recognition,347 CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 7229–7238, 2018.348
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. In 5th Interna-349 tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017,350 Conference Track Proceedings, 2017.351
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and352 approximate inference in deep generative models. In Proceedings of the 31th International353 Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pp. 1278–1286,354 2014.355
Omar Rivasplata, Csaba Szepesvari, John S Shawe-Taylor, Emilio Parrado-Hernandez, and Shiliang356 Sun. PAC-Bayes bounds for stable algorithms with instance-dependent priors. In Advances in357 Neural Information Processing Systems, pp. 9214–9224, 2018.358
Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero,359 and Raia Hadsell. Meta-learning with latent embedding optimization. In 7th International360 Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019,361 2019.362
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In363 Advances in Neural Information Processing Systems, pp. 4077–4087, 2017.364
Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012.365
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one366 shot learning. In Advances in neural information processing systems, pp. 3630–3638, 2016.367
Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim. Toward multimodal model-agnostic368 meta-learning. arXiv preprint arXiv:1812.07172, 2018.369
Xin Wang, Fisher Yu, Ruth Wang, Trevor Darrell, and Joseph E Gonzalez. Tafe-net: Task-aware370 feature embeddings for low shot learning. In Proceedings of the IEEE Conference on Computer371 Vision and Pattern Recognition, pp. 1831–1840, 2019.372
Kai Yu, Tong Zhang, and Yihong Gong. Nonlinear learning using local coordinate coding. In373 Advances in neural information processing systems, pp. 2223–2231, 2009.374
Fengwei Zhou, Bin Wu, and Zhenguo Li. Deep meta-learning: Learning to learn in the concept space.375 arXiv preprint arXiv:1802.03596, 2018.376
Luisa M. Zintgraf, Kyriacos Shiarlis, Vitaly Kurin, Katja Hofmann, and Shimon Whiteson. Fast377 context adaptation via meta-learning. In Proceedings of the 36th International Conference on378 Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 7693–7702,379 2019.380
Supplementary Materials for Localized Meta-381 Learning: A PAC-Bayes Analysis for Meta-Learning382 Beyond Global Prior383 This supplementary document contains the discussion of previous work, the technical proofs of384 theoretical results and details of experiments. It is structured as follows: Appendix A gives a detailed385 discussion of previous work. Appendix B presents the optimization method for LCC. Appendix C386 presents notations for prior predictor. Appendix D gives the proofs of the main results. Appendix387 D.1 and D.2 show the approximation error between LCC-based prior predictor and empirical prior388 predictor, expected prior predictor, respectively. They are used in the proof of Theorem 2. Next, in389 Appendix D.3 and D.4 we show the PAC-Bayes generalization bound of localized meta-learning390 in Theorem 2 and also provides the PAC-Bayes generalization bound of regular meta-learning in391 Theorem 1. Details of experiments and more empirical results are presented in Appendix E. Finally,392 we summarize the localized meta-learning algorithm in Appendix F.393
A RELATED WORK394
Meta-Learning. Meta-learning literature commonly considers the empirical task error by directly395 optimizing a loss of meta learner across tasks in the training data. Recently, this has been successfully396 applied in a variety of models for few-shot learning Ravi & Larochelle (2017); Snell et al. (2017);397 Finn et al. (2017); Vinyals et al. (2016). Although Vuorio et al. (2018); Rusu et al. (2019); Zintgraf398 et al. (2019); Wang et al. (2019) consider task adaptation when using meta-knowledge for specific399 tasks, all of them are not based on generalization error bounds, which is the in the same spirit as400 our work. Meta-learning in the online setting has regained attention recently Denevi et al. (2018b;a;401 2019); Balcan et al. (2019), in which online-to-batch conversion results could imply generalization402 bounds. Galanti et al. (2016) analyzes transfer learning in neural networks with PAC-Bayes tools.403 Most related to our work are Pentina & Lampert (2014); Amit & Meir (2018), which provide a404 PAC-Bayes generalization bound for meta-learning framework. In contrast, neither work provides a405 principled way to derive localized meta-knowledge for specific tasks.406
Localized PAC-Bayes Learning. There has been a prosperous line of research for learning priors407 to improve the PAC-Bayes bounds Catoni (2007); Guedj (2019). Parrado-Hernández et al. (2012)408 showed that priors can be learned by splitting the available training data into two parts, one for409 learning the prior, one for learning the posterior. Lever et al. (2013) bounded the KL divergence by a410 term independent of data distribution and derived an expression for the overall optimal prior, i.e. the411 prior distribution resulting in the smallest bound value. Recently, Rivasplata et al. (2018) bounded412 the KL divergence by investigating the stability of the hypothesis. Dziugaite & Roy (2018) optimized413 the prior term in a differentially private way. In summary, theses methods construct some quantities414 that reflect the underlying data distribution, rather than the sample set, and then choose the prior P415 based on these quantities. These works, however, are only applicable for single-task problem and416 could not transfer knowledge across tasks in meta-learning setting.417
B OPTIMIZATION OF LCC418
We minimize the 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.∀x, ∑ u∈C γu(x) = 1, (12)
where x̄ = ∑
u∈C γu(x)u. In practice, we update C and γ by alternately optimizing a LASSO419 problem and a least-square regression problem, respectively.420
C NOTATIONS421
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).
D THEORETICAL RESULTS422
D.1 PROOF OF LEMMA 1423
This lemma bounds the error between the empirical prior predictor ŵPi [k] and the LCC-based prior424 predictor w̄Pi [k].425
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. 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), (13)
where x̄j = ∑ u∈C γu(xj)u.426
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 equality427 holds since ∑ u∈C γu(xj) = 1 for all xj . The last inequality uses the assumption of (α, β)-Lipschitz428 smoothness of φv(·). This implies the desired bound.429
This lemma demonstrates that the quality of LCC approximation is bounded by two terms: the first term ‖xj − x̄j‖2 indicates x should be close to its physical approximation x̄, the second term ‖x̄j −u‖ implies that the coding should be localized. 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
1
mik ∑ xj∈Sik ( α‖xj − x̄j‖2 + β ∑ u∈C ‖x̄j − u‖22 ) ≤ [αcM + (1 + 5 √ dM)β] 2. (14)
It shows that the approximation error of local coordinate coding depends on the intrinsic dimension430 of the manifold instead of the dimension of input.431
D.2 PROOF OF LEMMA 2432
In order to proof Lemma 2, we first introduce a relevant theorem.433
Theorem 3. (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 (15)
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 δ ). (16)
The above theorem indicates that bounded differences in norm implies the concentration of f(X1:m)434 around its mean in norm, i.e., ‖f(X1:m)− E[f(X1:m)]‖ is small with high probability.435 Then, we bound the error between expected prior predictor wPi and the empirical prior predictor ŵ P i .436
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 δ )). (17)
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 , (18)
where R denotes the domain of x, say R = 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 3, 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 δ )). (19)
This implies the bound.437
Lemma 3 shows that the bounded difference of function Φv(·) implies its concentration, which can438 be further used to bound the differences between empirical prior predictor w̄Pi [k] and expected prior439 predictor wPi [k]. Now, we bound the error between expected prior predictor w P i and the LCC-based440 prior predictor w̄Pi .441
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 . (20)
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)‖ ) .
(21)
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− δ. (22) This gives the assertion.442
Lemma 2 shows that the approximation error between expected prior predictor and LCC-based prior443 predictor depends on the number of samples in each category and the quality of the LCC coding444 scheme.445
D.3 PROOF OF THEOREM 2446
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 learner Q = N (vQ, σ2vIdv). 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σ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 δ , (23)
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). (24)
Proof Our proof contains two steps. First, we bound the error within observed tasks due to observing447 a limited number of samples. Then we bound the error on the task environment level due to observing448 a finite number of tasks. Both of the two steps utilize Catoni’s classical PAC-Bayes bound Catoni449 (2007) to measure the error. We give here a general statement of the Catoni’s classical PAC-Bayes450 bound.451
Theorem 4. (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 G independent random
variables distributed according to X. Let π be some prior distribution over F (which must not depend on the samples X1, . . . , XG). For any δ ∈ (0, 1], the following bounds holds uniformly for all posterior distribution ρ over F (even sample dependent),
PXG1 ∼i.i.dX
{ E
X∼X E f∼ρ g(f,X) ≤ c 1− e−c
[ 1
G G∑ g=1 E f∼ρ g(f,Xg) + KL(ρ||π) + log 1δ G× c
] ,∀ρ } ≥ 1− δ. (25)
First step We utilize Theorem 4 to bound the generalization error in each of the observed tasks.452 Let i ∈ 1, . . . , n be the index of task. For task i, we substitute the following definition into the453 Catoni’s PAC-Bayes Bound. Specifically, Xg , (xij , yij),K , mi denote the samples and X , Di454 denotes the data distribution. We instantiate the hypotheses with a hierarchical model f , (v,w),455 where v ∈ Rdv and w ∈ Rdw are the parameters of meta learner (prior predictor) Φv(·) and456 base learner h(·) respectively. The loss function only considers the base learner, which is defined457 as g(f,X) , `(hw(x), y). The prior over model parameter is represented as π , (P, P ) ,458 (N (0, σ2vIdv),N (wP , σ2wIdw)), a Gaussian distribution (hyperprior of meta learner) centered at 0459 and a Gaussian distribution (prior of base learner) centered at wP , respectively. We set the posterior460 to ρ , (Q, Q) , (N (vQ, σ2vIdv),N (wQ, σ2wIdw)), a Gaussian distribution (hyperposterior of461 meta learner) centered at vQ and a Gaussian distribution (posterior of base learner) centered at wQ.462 According to Theorem 4, the generalization bound holds for any posterior distribution including463 the one generated in our localized meta-learning framework. Specifically, we first sample v from464 hyperposteriorN (vQ, σ2vIdv) and estimate wP by leveraging expected prior predictor wP = Φv(D).465 The base learner algorithm Ab(S, P ) utilizes the sample set S and the prior P = N (wP , σ2wIdw)466 to produce a posterior Q = Ab(S, P ) = N (wQ, σ2wIdw). Then we sample base learner parameter467 w from posterior N (wQ, σ2wIdw) and compute the incurred loss `(hw(x), y). On the whole, meta-468 learning algorithmAm(S1, . . . , Sn,P) observes a series of tasks S1, . . . , Sn and adjusts its hyperprior469 P = N (vP , σ2vIdv) into hyperposterior Q = Am(S1, . . . , Sn,P) = N (vQ, σ2vIdv).470 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. (26)
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. (27)
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, (28)
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 (29)
Then, according to Theorem 4, 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 ,
(30) for all observed tasks i = 1, . . . , n. Define δ′ = δi2 and combine inequality (29), 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, (31)
Using the notations in Section 3, 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. (32)
Second step Next we bound the error due to observing a limited number of tasks from the environment. We reuse Theorem 4 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. (33)
Using the term in Section 3, 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, (34)
Finally, by employing the union bound, we could bound the probability of the intersection of the events in (32) and (34) 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− δ. (35)
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− δ, (36)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 . This completes the proof.471
D.4 PROOF OF THEOREM 1472
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). Given 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 δ , (37)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 .473
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 hyperposteriorQ = N (wQ, σ2wIdw). Then the base learner algorithmAb(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 2, we first get an intra-task bound by using Theorem 4. 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,
(38) 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 ) , (39)
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. (40)
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− δ. (41)
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− δ, (42)
where c′1 = c1 1−e−c1 and c ′ 2 = c2 1−e−c2 . This completes the proof.474
E DETAILS OF EXPERIMENTS475
While the theorems consider bounded-loss, we use an unbounded loss in our experiments, we can476 have theoretical guarantees on a variation of the loss which is clipped to [0; 1]. Besides, in practice477 the loss function is almost always smaller than one.478
E.1 DATA PREPARATION479
We used the 5-way 50-shot classification setups, where each task instance involves classifying480 images from 5 different categories sampled randomly from one of the meta-sets. We did not employ481 any data augmentation or feature averaging during meta-training, or any other data apart from the482 corresponding training and validation meta-sets.483
E.2 NETWORK ARCHITECHTURE484
Auto-Encoder for LCC For CIFAR100, the encoder is 7 layers with 16-32-64-64-128-128-256485 channels. Each convolutional layer is followed by a LeakyReLU activation and a batch normalization486 layer. The 1st, 3rd and 5th layer have stride 1 and kernel size (3, 3). The 2nd, 4th and 6th layer have487 stride 2 and kernel size (4, 4). The 7th layer has stride 1 and kernel size (4, 4). The decoder is the488 same as encoder except that the layers are in reverse order. The input is resized to 32 × 32. For489 Caltech-256, the encoder is 5 layers with 32-64-128-256-256 channels. Each convolutional layer is490 followed by a LeakyReLU activation and a batch normalization layer. The first 4 layers have stride 2491 and kernel size (4, 4). The last layer has stride 1 and kernel size (6, 6). The decoder is the same as492 encoder except that the layers are in reverse order. The input is resized to 96× 96.493 Base Model The network architecture used for the classification task is a small CNN with 4 con-494 volutional layers, each with 32 filters, and a linear output layer, similar to Finn et al. (2017). Each495 convolutional layer is followed by a Batch Normalization layer, a Leaky ReLU layer, and a max-496 pooling layer. For CIFAR100, the input is resized to 32× 32. For Caltech-256, the input is resized to497 96× 96.498
E.3 OPTIMIZATION499
Auto-Encoder for LCC As optimizer we used AdamKingma & Ba (2015) with β1 = 0.9 and500 β2 = 0.999. The initial learning rate is 1× 10−4. The number of epochs is 100. The batch size is501 512.502
LCC Training We alternatively train the coefficients and bases of LCC with Adam with β1 = 0.9503 and β2 = 0.999. In specifics, for both datasets, we alternatively update the coefficients for 60 times504 and then update the bases for 60 times. The number of training epochs is 3.The number of bases is505 64. The batch size is 256.506
Pre-Training of Feature Extractor We use a 64-way classification in CIFAR-100 and 150-way507 classification in Caltech-256 to pre-train the feature embedding only on the meta-training dataset. For508 both CIFAR100 and Caltech-256, an L2 regularization term of 5e−4 was used. We used the Adam509 optimizer. The initial learning rate is 1× 10−3, β1 is 0.9 and β2 is 0.999. The number of epochs is510 50. The batch size is 512.511
Meta-Training We use the cross-entropy loss as in Amit & Meir (2018). Although this is inconsistent512 with the bounded loss setting in our theoretical framework, we can still have a guarantee on a variation513 of the loss which is clipped to [0, 1]. In practice, the loss is almost always smaller than one. For514 CIFAR100 and Caltech-256, the number of epochs of meta-training phase is 12; the number of epochs515 of meta-testing phase is 40. The batch size is 32 for both datasets. As optimizer we used Adam with516 β1 = 0.9 and β2 = 0.999. In the setting with a pre-trained base model, the learning rate is 1× 10−5517 for convolutional layers and 5× 10−4 for the linear output layer. In the setting without a pre-trained518 base model, the learning rate is 1× 10−3 for convolutional layers and 5× 10−3 for the linear output519 layer. The confidence parameter is chosen to be δ = 0.1. The variance hyper-parameters for prior520 predictor and base model are σw = σv = 0.01. The hyperparameters α1, α2 in LML and ML-A are521 set to 0.01.522
E.4 MORE EXPERIMENTAL RESULTS523
We also compare with two typical meta-learning few-shot learning methods: MAML (Finn et al.,524 2017) and MatchingNet (Vinyals et al., 2016). Both two methods use the Adam optimizer with initial525 learning rate 0.0001. In the meta-training phase, we randomly split the samples of each class into526 support set (5 samples) and query set (45 samples). The number of epochs is 100. For MAML, the527 learning rate of inner update is 0.01.528
In Figure 5, we demonstrate the average test error of learning a new task based on the number of529 training tasks, together with the standard deviation, in different settings (with or without a pre-trained530 feature extractor). We can find that all PAC-Bayes baselines outperform MAML and MatchingNet.531 Note that MAML and MatchingNet adopt the episodic training paradigm to solve the few-shot532 learning problem. The meta-training process requires millions of tasks and each task contains limited533 samples, which is not the case in our experiments. Scarce tasks in meta-training leads to severely534 meta-overfitting. In our method, the learned prior serves both as an initialization of base model and535 as a regularizer which restricts the solution space in a soft manner while allowing variation based on536 specific task data. It yields a model with smaller error than its unbiased counterpart when applied to a537 similar task.538
F PSEUDO CODE539
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. (12). 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 (11), 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

Review summaries:
The paper presents an algorithm for offline meta-learning, where tasks are drawn from a distribution and presented to a learner sequentially, the objective being to use accumulated knowledge in order to facilitate the learning of new tasks. The algorithm is motivated from the PAC-Bayes theory of generalization, extended in recent years to the meta-learning setup, and provides a new localized approach where the prior used for a novel task is allowed to depend on the data from the new task in addition to all previous tasks. They make use of a previously proposed local learning method (LCC) that leads to extra flexibility and to a tightening of the meta-learning bounds, and provide an algorithm based on these bounds from which a learning algorithm is derived based on minimization of the upper bound. Empirical results are provided demonstrating the efficacy of the method and comparing to other recent approaches.