Localized Meta-Learning: A PAC-Bayes Analysis for Meta-Leanring Beyond Global Prior
Authors: Chenghao Liu
Tao Lu
Doyen Sahoo
Yuan Fang
Steven C.H. Hoi.
Venue:  (2020)
Keywords: localized meta-learning
PAC-Bayes
meta-learning

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

36 required to extract these patterns simultaneously. This could be a challenging problem represent it with global hyperposterior since the most significant patterns in the first task could be irrelevant Under review as a conference paper at ICLR 2020
LOCALIZED META-LEARNING A PAC-BAYES ANAL- YSIS FOR META-LEARNING BEYOND GLOBAL PRIOR
Anonymous authors Paper under double-blind review
ABSTRACT
Meta-learning methods learn the meta-knowledge among various training tasks and aim to promote the learning of new tasks under the task similarity assumption. However, such meta-knowledge is often represented as a fixed distribution, which is too restrictive to capture various specific task information. In this work, we present a localized meta-learning framework based on the PAC-Bayes theory. In particular, we propose an LCC-based prior predictor that allows the meta learner to adaptively generate local meta-knowledge for specific tasks. We further develop practical algorithm with deep neural network based on the bound. Empirical results on real-world datasets demonstrate the efficacy of the proposed method.
10
INTRODUCTION
Recent years have seen resurgence of interest in the field of meta-learning, starningtto-leare (Thrun & Pratt 2012), especially for empowering deep neural networks the capability of fast adapt- tasks just as humans (Finn al. [017 Ravi & Larochelle] (017). More concretely, the neural networks are trained from a sequence of datasets, associated with different learning tasks sampled from meta-distribution (also called task environment (Baxter) 2000) Maurer] (2055). The principal aim of meta learner is to extract transferable meta-knowledge from observed tasks and facilitate the learning of new tasks sampled from the same veta-distribution. The performance is measured by the generalization ability from finite set of observed tasks, which is evaluated by learning related unseen tasks. For this reason, there has been considerable interest in theoretical bounds on the generalization in terms of the meta-learning algorithm (Denevi et al. 2018b a).
12
ing
14
15
16
17
18
19
21
One typical line work (Pentina & Lampert 2014; Amit Meir 2018 use PAC-Bayes bound to analyze the generalization behavior of the meta learner and quantity the relation between the ex- pected loss on new tasks and the average loss on the observed tasks. In this setup, we formulate meta-learning
22
23
hierarchical Bayes. Accordingly, meta-knowledge is instantiated as global dis- tribution over all possible priors, which we call hyperprior and is chosen before observing training tasks. Each prior is distribution over family of classifiers w.r.t. particular task. To learn versa- 27 tile meta-knowledde across tasks, the meta learner observes sequence of training tasks and adjusts its hyperprior into hyperposterior distribution over the of priors. To solve leamner produces posterior distribution over family of classifiers based on the associated sample set and the prior generated by the hyperposterior.
25
task, the base
29
30
31 However, such meta-knowledge is shared across tasks. The global hyperposterior is rather generic, typically not well-tailored to various specific tasks. Consequently, it leads sub-optimal perfor- mance for any individual prediction task. As motivational example, suppose we have two dif-
32
33
34 ferent tasks: distinguishing motorcycle versus bicycle and distinguishing motorcycle versus car.
35 Intuitively, each task uses distinct discriminative patterns and thus the desired meta-knowledge is
38 or even detrimental to the second task.
Hence, are motivated to pursue meta-learning framework to effectively define the hyperpos- 40 terior. The inspiration comes from the PAC- PAC-Bayes literature on data distribution dependent priors (Ctonni 2007 Parrado-Herández al. 2012 Dziugaite & Roy 2018). The choice of posterior
42 in each task is constrained by the need to minimiee the relative entropy between prior and pos- terior since this divergence forms part of the bound and is typically large in standard PAC-Bayes

---

Under review as a conference paper at ICLR 2020
approaches (Lever et al. 2013). Thus, choosing appropriate prior for each task which is close to the related posterior could yield improved generalization bounds.
45
Inspired by this, propose Localized Meta-Learning (LML) framework. Instead of formulating koww-enowledge as a global hyperposterior, we learn a conditional hyperposterior given task data distribution that allows meta learner to adaptively generate an appropriate prior for However, the task data distribution unknown, and our only perception for it via the associated sample Nevertheless, if the conditional hyperposterior is relatively stable to perturbations of the sample set, then the generated prior could still reflect the underlying task data distribution, resulting a generalization bound that still holds with smaller probability. Following this intuition, the dependence of a conditional hyperposterior on the task data distribution is parameterized by prior al., 2009). In particular, the classifier in each task is specialized to a parametric model, including deep neural network, the proposed LCC-- based prior predictor predicts the model parameters using the sample set by exploiting the local information on the latent manifold. LCC-based prior predictor is invariant under permutations of its inputs and could be further used for unseen tasks.
47
task.
49
50
51
52
53
54
predictor using Local Coordinate Coding (I.CC)
55
56
58
The main contributions of this work include: (i) We present a localized meta-learning framework which provides a means to tighten the original PAC-Bayes meta-learning bound (Pentina & Lam- pert Amit & Meir 2018) by minimizing the task-complexity term by choosing data-dependent 62 prior; (ii) We propose an LCC-based prior predictor, an implementation of conditional hyperposte- rior, to generate local kettlknooweddge for specific task; (iii) We derive practical localized meta- learning algorithm for deep neural networks by minimizing the bound; (iv) Experimental results demonstrate improved performance over meta-learning method in this field.
60
Amit
64
65
86
PRELIMINARIES
67
2.1
LOCAL COORDINATE CODING
68
We first review some definitions Local Coordinate Coding (LCC) Yu et al. 2009) based on which develop the proposed LCC-based prior predictor.
Definition 1. (Lipschitz Smoothness (Yu et al. 2009).)
A function f(x) on Rd is a ( 3)-Lipcchitz
70
smooth w.r.f. norm I1 [ f(x')l I a a x' and [l -(x)) fx(x) (x' x)] S
71
0||x - x'1 I
72
Definition 2. (Coordinate Coding Yu et al. 2009).) A coordinate coding is pair (r; C), where C. C Rdd. is set of anchor points, and 7 is map of x E Rdd "xu(x)]uEC E R such that _x()) = 1. It induces the following physical approximation of x in Rd 7(x)
75
76 Enec Tu(x)ux
Definition 3. (Latent Manifold (Yu al. 2009).) A subset M C Rd called a smooth manifold with intrinsic dimension d := d.M if there exists a constant CM such that given any x E M, there exists bases un (x(x)..... ux(x)) ) E RRd so that Vix E M:
inf |x - RRRIC
Σ (z)1(x))22 S cm/lx' - xx12
where 7 .. Ta) are the local codings w.r.t. the bases.
Definition 4. (Covering Number (Yu et al.) 2009).) The covering number (c, is the smallest cardinality of an e-ccover C C M. That is
sup in - S.. xEM
78 Definition 2 and imply that any point in RR can be expressed as a linear combination set of anchor points. Later, we will use them to develop the prior predictor.
2.2 PAC-BAYES META-LEARNING
81 In order to present the advances proposed in this paper, we next recall some definitions in PAC- PAC-Bayes theory for single-task learning and meta-learning (Catoni 2007 Baxter 2000
Pentina & Lampert
2

---

Under review as a conference paper at ICLR 2020
Amit & Meir 2018). In the context of classification, we assume all tasks share the same input space X, output space y. space of classifiers (hypotheses) H C {h : X + ) and loss function L y y + [0. 1]. The meta learner observes tasks in the form of sample sets S SI..... SS. task is denoted by m,. Each observed task consists of a set of i.i.d. The number of samples 1 1= which is drawn from data distribution S; D. Following the samples S; {(X}, Vý)
2014
84
86
87
88
meta-lcarning setup in (Baxter 2000), we assume that each data distribution D. is generated i.i.d. from the same meta distribution т. Let h(x) be the prediction of x, the goal of each task is to find a classifier h that minimizes the expected loss Ex~De(h(x), v). Since the underlying 'true' data distribution D; is unknown, the base learner receives a finite set of samples S; and produces an "optimal" classifier h = As(S,) with a deterministic learning algorithm As(-) that will be used to predict the labels of unseen inputs.
89
90
91
95
94 PAC- Bay-e theory studies the properties of randomized classifier, called Gibbs classifier. Let Q be a posterior distribution over H. to make a prediction, the Gibbs classifier samples a classifier h E H according to Q and then predicts a label with the chosen h. The expected error under data distribution D and empirical error on the sample set S are then given by averaging over distribution Q, namely er( Q)
95
97
( (((()))))()((())))))))))))))())) (z), y) and (r)) En-q Σラ= ((h(2,) vj). respectively. Then, generalization bound of Catoni (2007) in simplified form
get the following 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 > O, the following inequality holds uniformly for all posteriors distribution Q with probability at least 1 - 8,
cr())= S 1 (r(Q)) + KL(QIIP) + log
mc
101
The PAC-Bayes bound holds uniformly for all Q. it also holds for the data dependent Q. By choosing the posterior Q that minimizes the PAC-Bayes bound, we obtain an learning algorithm with general- ization guarantees. Note that the value e allows to control the trade-off between the empirical error and the complexity term.
103
104
The goal of the meta learner is to extract meta- kntwleenwweedee 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 distribution over classifiers H. In each task, the base learner produces posterior Q = As,S, P) over H. based on sample set and a prior P. All tasks are Iearned through the same learning procedure. The meta learner treats the prior P itself as a random variable and assumes the meta- knowledge in the form of a distribution over all possible priors. Let hyperprior be an initial distribution over priors, meta learner uses the observed tasks to adjust its original hyperprior P into hyperposterior @ from the learning process. The quality of the hyperposterior expected task error of learning new tasks using priors generated from it, which is formulated as:
measured by the
er( () -EP-olE (,)) er = P),
(2)
Accordingly, the empirical counterpart of the above quantity is given by:
ér (Q) = Ep-e ér(Q = Ao(S,, P)).
3 PAC-BAYES META- BOUND WITH GAUSSIAN RANDOMIZATION
108
Based on the above definition, Pentina & Lampert 2014) and Amit & Meir 2018)
present meta-
107
learning PAC-Bayes generalization bounds w.r.t. hyperposterior Q by using McAllester's 's single-task
108
bound (McAllester 1999). Here we present new meta-learning generalization bound with Gaus- sian randomization by using Catoni's bound in Eq. (T) In particular, the classifier h is parameterized as fow with w E Rdw, The prior and posterior is distribution over the set of all possible parameters
109
111 w. We choose both the prior P and posterior Q to be spherical Gaussians, iee. P =V ((w", P o and 2w?? of Idw) The mean w is a random variable distributed first according to the
113 hyperprior P, which we formulate as A A((0, o Iaw) ). and later according to hyperposterior Q. which task i, we first sample the mean of prior
model N(w 2 [T Ja When encountering
3

---

Under review as a conference paper at ICLR 2020
w. from the hyperposterior NWw ow Idw and then use it as basis to learn the mean of poste- (.S.PP. P), as shown in Figure llfft). Then, we could derive the following PAC-Bayes leta-lea bound.
116 rior w (S,,
117
Theorem 2. Consider the Meta-Learning framewww, given the hyperprior P = NO, af afTd,)
then any hyperposterior 2, any C1,02 C2 and any 8 E (0, 1] with probability 2 1 we have,
GC
& 20 no
GP2
er(2) Scicee(())
E wP
2 w 20 w
202mm;0
202nim;00
1=
2n
c
+
log
log
(4)
Comm,
'2"
5
nio
8
w
118
where 0g = 1-
and C2
Proof. See Appendix B.3 for the proof.
120
Notice that the expected task generalization error is bounded by the empirical multi-task error plus two complexity terms. The first term demonstrates the environment-compllxity which converges to zero an infinite number tasks are observed from the task environment (n - oo), while the second is the task-complexity of the observed tasks which converges to zero when the sufficient samples in each task is observed (m, + oo). Besides, the derived bound converges at the rate
122
124
125
of O instead of O m
in (Pentina & Lampert 2014 Amit & Meir 2018), due the use of
126
Catoni's bound.
127
4
PAC-BAYES LOCALIZED META-LEARNING
128
4.1
OVERALL FRAMEWORK
Our motivation stems from a core challenge in PAC-Bayes meta-learning bound in 41 wherein the d.d. [Ew w0l is typically vital to the bound and so finding the tightest possible bound generally depends on minimizing this term. It is obvious that the optimal
130
complexity term Ei= Zoyam,
&cc.Ew?
132
w is Ei= 20amm:04 However, if the learned posteriors for each task are mutually exclusive, i.e.,
133
one learned posterior has negative effect on another task, this term could be inevitably large.
w 2 the mean of hyperposterior Q and this term naturally indicates the divergence between the
134
mean of prior w sampled from the hyperposterior Q and the mean of posterior w in each task. Therefore, we propose to adaptively choose the mean of prior w?" according to task i. is obvious that the complexity term vanishes if we set w!" = w but the prior P: in each task has to be chosen independently the sample set S.. Fortunately, the PAC-Bayes theorem allows us to choose prior upon the data distribution D. Therefore, we propose a prior predictor Φ Dm - w.P which receives task data distribution n and outputs the mean of prior w". In this way, the generated priors could focus locally on those regions of model parameters that are of particular interest in solving specific tasks.
135
136
137
138
140
142
Particularly, the prior predictor is parameterized as o, with Rd We abuse notation P and Q and assume v as a random variable distributed first according to the hyperprior P, which we reformulate as (0 of ), and later according to hyperposterior Q, which reformulate as N ot J. Given a new task i, we first sample v from hyperposterior NVv o Ja.) and estimate the mean of prior w!" by leveraging prior predictor w. &, (D!"). Then, the base
144
145
146
leamner utilizes the sample set S, and the prior P: N(W,,, oz Iaw.) to produce mean posterior (S,, P.). as illustrated in Figure right).
149
w
150
4.2
LCC-BASED PRIOR PREDICTOR
To make w close to 2 in each task, the prior predictor is required to (i) uncover the tight relation- ship between the sample set and model parameter. Intuitively, features and parameters yield similar local and global structures in their respective spaces in the classification problem. Features in the
152
153
4

---

Under review as a conference paper at ICLR 2020
Task
Task
Task
Future Task-
Task 1
Task 2
Task n
Future Task-
$2-D7
- ti
S-D
S D1-D1 m
S D2
Sm Dr
S-Dm
Prior
Prior
Learner
Meta Learner (Prirr Predicter oo
Base Learner
Aglibul dotributin
w
w
P D
We
w
Figure 1: Comparison between meta-learning (left) and localized meta-learning (right). In regular meta-lcarning, the mean of prior w is sampled from global hyperposterior distribution Q N(w* o Iaw)) the localized meta-learning, wP is produced by prior predictor (D").
154
same category tend be spatially clustered together while maintaining the separation between dif- ferent classes. Take linear classifiers as an example, let wi be the parameters w.r.t. category k, the separability between classes is implemented as x Wk. which also explicitly encourages intra-class compactness. A reasonable choice of Wa is to maximize the inner product distance with the input features the same category and minimize the distance with the input features of the non-belonging categories. Besides, the prior predictor should be (ïi) category-agnostee agnostic since it will be used contin- uously as new tasks and hence new categories become available. Lastly, it should be (iii) invariant under permutations of its inputs.
155
156
158
160
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 al. (2017) learns metric space across tasks such that when represented in this embedding, pro- totype (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 be- tween 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 prob- lem which is shared across tasks. Once this mapping has been learned on observed tasks, due to the structure-preserving
property, it could easily generalized to new tasks. Formally, be a K-class classification problem. Then the parameter of the classifier in task is represented as w; [K]]] The prior predictor for class k could be defined as:
each task
w, = [w][1]...... w. [k),.....
[kk),....
[K] = 2 (Dth =
E Sum
Σ (x(x)),
(5)
XjESit.
where d-(-): Rd Row is the feature embedding function, m. is the number of samples belong- ing to category k. Si. and Due are the sample set and data distribution for category & in task i. We call this function the expected prior predictor. Since data distribution D& considered unknown and our only insight as to Di 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 [k] (S(a))
Σ Ov(x)),
(6)
X/ESta
182 which call the empirical prior predictor. Although we can implement the embedding func- tion (.).) with a multilayer perceptron (MLP), both input x and model parameter w are high- dimensional, making the empirical prior predictor év(-) difficult to learn. According to Definition 165 3. any points on the latent manifold can be approximated by a linear combination of set anchor points. Inspired by this, if the anchor points are sufficiently localized, the empirical prior predic- tor (S) can also be approximated by a linear function w.r.t. set of codings. Accordingly, propose an bCC- prior predictor, which is defined as:
183
188
w = (Stk)
Σ (u)),
(7)
Mik X, KyES& uEC
5

---

Under review as a conference paper at ICLR 2020
where (u) E Rdw is the feature embedding of base R.. As such, the pa- 170 rameters of bCs-b prior predictor w.r.t category can be represented as Va = [Pv, (u)), ), Pv, (uz)..... Dv (uc))) Lemma iillustrates the upproximation error.
Local linearity
900
Manifold
Figure 2: A geometric view of Local Coordinate Coding. Given set of anchor points, if data lie on a manifold, the empirical prior predictor (S) can be locally approximated by a linear function w.r.t. the coding. Given all bases, (S) can be globally approximated.
171
Lemma 1. (Empirical Pior Predictor Approximation) Given the definition of w [k] and w w![k] in Eq. (6) and Eq. (7). let (7, C) be an arbitrary coordinate coding on R and 6 be an (a, B)-isschiitzz smooth function. We have for all x E Rd
|| | [b] [
Σ (alx) XjESik
x, +
ull²) On, C)2
Mik
uEC
where X2 =Eueo Yu (xxx),. Then given any >> 0, there exists coding (7, C) such that
IC| (1
0g,0(7, & JacM + (1+ 5 dm)3)e.
(9)
Proof. See appendix B.I for the proof.
175
The first inequality of Lemma demonstrates that a good LCC-based prior predictor should make x close to its physical approximation X and should be localized. The second and third inequality show that a set of anchor points has cardinality (e, linearly approximated using LCC up to accuracy O D(VdMe²). The complexity of the LCC coding scheme depends only the number of anchor points |C| instead of the input dimension. In fact,
175
emprical prior predictor can be
176
178
small |C| usually sufficient to achieve good approximation.
Optimization of LCC. We minimize the first inequality in (8) to obtain set of anchor points. As with YYu et al.] 2009), we simplify the localization error term by assuming & = x, and then we optimize the following objective function:
arg min T.C
Σ allx;
x1
+
3
Σ xx) - u//
s.t.
[u(x) = 1, VX,
(10)
i=1
ES
uEC
nEC
where Euec Tu(x).. In practice, update C and by alternately optimizing LASSO problem and a least-square regression problem, respectively.
180
181
4.3 PAC-BAYES LOCALIZED META-LEARNING BOUND WITH GAUSSIAN RANDOMIZATION
182
In order derive a PAC-Bayes generalization bound for localized learning we first bound the approximation error between expected prior predictor and -CC-- prior predictor.
183
Lemma 2. Given the definition of w" and w in Eq. (5) and 7 let X be a compact set with
radius R, i.e., VX E X. 1|x x' < R. For any 8 E (0. with probability 2 11 ō, we have
K
aR
log( 1 ()()))) + 00,
||wP w 1 < Σ
(1 +
(11)
miss
k=1

---

Under review as a conference paper at ICLR 2020
Proof. See appendix [B.2 for the proof.
185
Lemma shows that the approximation error between expected prior predictor and LCC-based prior predictor depends on (i) the concentration of prior predictor and (ii) the quality of LCC coding scheme. The first term implics the number of samples for each category should be larger for better approximation. This is consistent with the results of estimating the center of mass (Cristianini & Shawe- Taylor, (004). Based on Lemma 2 we have the following PAC-Bayes LML bound.
187
189
Theorem 3. Consider the Localized Meta-Learning (LML.) framework, give the hyperprior P AO Lodd), then for any hyperposterior Q, any C1, C2 > 0 and any ô E (0,1) with probability 2 å we have,
GP 20gramo0
d
er( SciGer(
Σ 1=1
+
1
Σ 1=1 egnemo
IEW; - 2 (Sel
2cino
K
aR
4n logi
)) + O +000(1100) + dw dwkk( K{( 2x)3
+
0 k=1
Miik
8
Ow
An
dj
+
log
log
(12)
o
6
2c n
where e4 = I--a and cg =
m
To gel a better understanding, we further simplify the
I---
notation and obtain that
GC
&
er(2) (Q)g)(()) +
+
|E 2 eve (S:))l
2
2cnno?
c2nmo
+ const(a,
m.).
(13)
190
Proof. See appendix B.3 for the proof.
Similarly with the PAC-Bayes meta-learning bound in Theorem 2 and the bounds in (Pentina & Lampert 2014 Amit & Meir 2018), the expected task error er (Q) is bounded by the empirical terms. The main innovation here is to exploit the potential to choose the mean of prior w based on task data S. Intuitively, if the selection of the LCCC-bsed prior predictor is appropriate, it will narrow the divergence between
192
193
task error er( () plus the task complcomylyxity and
194
195
the mean of prior w!" sampled from the hyperposterior Q and the mean of posterior w in each task. Therefore, the bound can be tighter than the ones in the meta-learning framework. Our em- pirical study in Section 5 illustrates that the algorithms derived from this bound can achieve better performance than the methods derived from standard PAC-Bayes meta- meta-learning bounds.
196
198
200
When one choosing the LCC-based prior predictor (-),), the number of anchor points |C]. there balance between accuracy and simplicity. As increase |C). it will essentially increase the expressive power of (.) and reduce the complexity term ||Ew c (2) However, at the
202
same time, it will increase the complexity term || and make the bound loose. If we set |C' to 1, is degraded to the regular meta-learning framework.
204
205
4.4
LOCALIZED META-LEARNING ALGORITHM
Since the bound in 27 holds uniformly w.r.t. Q, the guarantees of Theorem also hold for the resulting learned hyperposterior Q = (v8 Ta, so the mean of prior w sampled from the leamed hyperposterior work well for future tasks. The PAC-Bayes localized meta-learning bound in
27 can be compactly written as
1
Σ Bér,(Q A P)) + a1 / 1
Σ
Q2 Ew m
L (S.))1
(14)
where a1, 02 > 0 are hyperparameters. For task i, the learning algorithm As(-) can be formulated as W = arg min (er:(Q; = (W Ia Following Amit & Meir 2018)), we jointly opti-

---

Under review as a conference paper at ICLR 2020
mize the parameters of LCC-based prior predictor and the parameters of classifiers in each task W1, W Wn, which is formulated as
arg min
Σ Ber, (w.)(w.) + anl 2 + Σ Ew e (S.)]l.
(15)
W.W
We can optimize v and via mini-batch SGD. The details of algorithms for meta-training are given in Algorithms]] The expectation over Gaussian distribution and its gradient can be efficiently
Algorithm 1 Localized Meta-I.errnnng (LML.) algorithm
Input: Data sets of observed tasks: Si,..., Sn..
Output:
Learned prior predictor & parameterized by v.
Initialize E Rdv and w; Rdd for ...., n.
Construct LCC scheme (y, C)) from the whole training data by optimizing Eq. while not converged do for each task i ( [1.....n] do
10
Sample random mini-batch from the data S St. Approximate (er;(w;) using Sy
end for Compute the objective in 15). i.. J Ei= (er)(w;) + 211lv2112 + E II
22 my
& (S:))l
Evaluate the gradient of w.r.t {v, Wi...., w.. using backpropagation. Take an optimization step.
end while
estimated by using the re-parameterization trick (Kingma & Welling 2014 Rezende et al. 2014 208
209
For example, sample from the posterior N N(w o wwwdw first draw & N Ldw and then apply the deterministic function w + C or where @ is an element- multiplication.
5
EXPERIMENTS
Caltech-258
Acc uracy on New Task(N))
CIFAR-100
Caltech-258
Accuracy on New Tack(%)
CIFAR-100
2
Accuracy New
2
LMI
Hi-k MARe
3ep
Mi:4M
Accurale
WARk
Number Tasks
Number Tasks
Number Tasks
Number Tasks
With pre-trained feature extractor
(b) Without pre-trained feature extractor
Figure 3: The average test accuracy of learning a new task for different number training tasks (IC) = 64).
Accuracy New Toak(S)
Caltech-256
Caltech-256
CIFAR-100
- LML
+ MLA
LML
MLA
Divergence
Divergence
8.6
5.4
9.2
A Number
Number 138
22 124
Number Tasks
Number Tasks
Figure 4: (a) The impact of the number of bases |C| in LCC. (b) The divergence value (normalized) between the mean generated prior w and the mean of learned posterior w
5.1 DATASETS AND SETUP
213 We use CIFAR-100 and Caltech-25t in our experiments. CIFAR-100 100 (rizhevsky 2009) contains
60,000 images from 100 fine-grained categories and 20 coarse-level categories. As in (Zhou al.
8

---

Under review as a conference paper at ICLR 2020
2018), we use 64, 16, and 20 classes for meta-training, meta-validatte and meta-testing, respec- tively. Caltech-256 has 30,607 color images from 256 classes (Griffin et al. 2007). Similarly, we split the dataset into 150, 56 and 50 classes for meta-training, meta- veta--vlidation, and meta-testing. We consider 5-way classification problem. Each task is generated by randomly sampling 5 categories
216
218
219
and each category contains 50 samples. The base model uses the convolutional architecture in (Finn) et al. 2017)), which consists of 4 convolutional layers, each with 32 filters and fully-connected
220
221
layer mapping to the number of classes on top. High dimensional data often lies on some low di- mensional manifolds. We utilize an auto-encoder to extract the semantic information of image data and then construct the LCC scheme based on the embeddings. The parameters of prior predictor and base model are random perturbations in the form of Gaussian distribution. We design two different meta-learning environment setting to validate the efficacy of the proposed method. The first one uses the pre-trained base model as an initialization, which utilizes all the meta-training classes (64-class classification in CIFAR- 100 case) to train the feature extractor. The second one uses the random initialization. We compare the proposed LML method with ML-PL method (Pentina & Lampert 2014), ML-AM method (Amit & Meir 2018) and ML-A which is derived from Theorem [ In these methods, we their main theorems about the PAC-Bayes generalization bound to derive the objec- live for the algorithm. We also compare with two typical meta-learning few-shot learning methods: MAML (Finn et al., 2017) and MatchingNet (Vinyals al., 2016). To ensure fair comparison, all
222
223
225
227
229
231
232
233
approaches adopt the same network architecture and pre- pre-trained feature extractor.
234
5.2
RESULTS
In Figure 3 we demonstrate the average test error of learning a new task based on the number of training tasks different settings (with or without pre-trained feature extractor). It is obvious that the performance continually increases methods. This is consistent with the generalization bounds that the complexity term converges to zero if large numbers of tasks are observed. ML-A consistently outperforms ML-PL and ML-AM since the bound w.r.. ML-A in Theorem 2 converges at the rate of O())) while the bounds w.rt.
236
increase the number of training tasks for all the
238
240
241
ML-PL and ML-AM converge at the rate of 0 (m)) This demonstrates the importance of using tight generalization bound. Our proposed LML significantly outperforms the baselines, which validates the effectiveness of the proposed LCC-based prior predictor. It is a more suitable representation for knowlln than the traditional global hyperposterior in ML-A, ML-AM, and ML-PL.
243
245
Moreover, we can find that all PAC-Bayes baselines outperform MAML and MatchingNet. Note that MAML and MatchingNet adopt the episodic training paradigm to solve the few-shot learn- ing problem. The meta-training process requires millions of tasks and each task contains limited samples, which is not the case in our experiment. Scarce tasks in meta-training leads severely meta-overfitting. In our method, the learned prior serves both as an initialization of base model and as a regularizer which restricts the solution space while allowing variation based on specific task data. It yields a model with smaller error than its unbiased counterpart when applied to a similar task.
247
248
249
250
251
252
253
Finally, we observe that if the pre-trained feature extractor is provided, all of these methods do better than meta-training with random initialization. This is because pre-trained feature extractor can be regarded as data-dependent hyperpior. is closer to the hyperposteior than the randomly initialized hyperprior. Therefore, it reduces the environment complexity term and improves the generalization performance.
254
255
296
In Figure 4bb) we show the divergence between the mean of generated prior wP from meta model and the mean of learned posterior w for LML and ML-A. This further validates the effectiveness of the LCC-based prior predictor which could narrow the divergence term and thus tight the bound. In Figure 4()) we vary the number of bases |C| in LCC scheme from 4 to 256, the optimal value is around 64 in both datasets. This indicates that LML is sensitive to the number of bases |C], which further affects the quality of LCC-based prior predictor and the performance of LML.
258
280
262
263
6 RELATED WORK
264
285
Meta-Learning. Meta-learning literature commonly considers the empirical task error by directly optimizing a loss of meta learner across tasks in the training data. Recently, this has been success-
286

---

Under review as a conference paper at ICLR 2020
fully applied in variety of models for few-shot learning (Ravi & Larochelle 2017: Snell et al.
2017| Finn et al. 2017]] Vinyals et al., 2016). Although Vuorio et al. (2018); Rusu et al. (2019);
288
Zintgraf et al. (2019); Wang et al. (2199) consider task adaptation when using meta-knowlee
for specific tasks, all of them are not based on generalization error bounds, which is the focus of our
270
work. Meta-learning in the online setting has regained attention recently (Denevi et al. 20T8b a
272
2019 Balcan et al., 2019), in which online-to-batch conversion results could imply generalization bounds. Galanti al. (2016) analyzes transfer learning in neural networks with PAC-Bayes tools.
273
274
Most related to our work are (Pentina & Lampert] 2014] Amit & Meir 2018) which provide a Pay-Bayes generalization bound for meta-learning framework. In contrast, neither work considers
275
localized meta-knowledge for specific tasks.
277
Localized PAC-Bayes Learning. There has been a prosperous line of research for learning priors to improve the PAC-Bayes bounds Catoni (2007); Guedj (2019). (Parrado-Hernández et al. 2012) showed that priors can be learned by splitting the available training data into two parts, one for
278
279
learning the prior, one for learning the posterior. (Lever et al. 2013) derived an expression for the
281
overall best prior, i.e. the distribution resulting in the smallest possible bound value and bounded
the KL divergence by term independent of data distribution. Recently, (Rivasplata et al. 2018) bounded the KL divergence by investigating the stability of the hypothesis. (Dziugaite & Roy 2018)
283
284
optimized the prior term in differentially private way. In summary, theses methods construct some
285
quantities that reflect the underlying data distribution, rather than the sample set, and then choose
286
the prior P based on these quantities. These works, however, are only applicable for single-task problem and could not transfer knowledge across tasks in meta-lcarning setting.
287
7
CONCLUSION
288
289
This work contributes a novel localized meta- meta-learning framework from a theoretical perspective. We propose a generalization bound based on PAC-Bayes theory with Gaussian randomization. Instead of formulating meta-knowledge as global distribution, we propose LCC-based prior predictor to output local meta-knowledge by using task information. We further develop a practical algorithm with deep neural network based the bound. An interesting topic for future work would be to explore other principle to construct the prior predictor and apply the localized meta-learning frame-
290
292
294
work more realistic scenario that tasks are sampled non-i.idd. from environment. Another challenging problem is to extend our techniques to derive localized meta-learning algorithms for regression and reinforcement learning problem.
296
298
REFERENCES
299
Ron Amit and Ron Meir. Meta-leariin by adjusting priors based on extended PAC-Bayes theory. In International Conference on Machine Learning, pp. 205 215,214,777 2018.
300
Maria- Maria-Florina Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 424-433, 2019.
302
303
304
Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12: 149-198, 2000.
306
Luca Bertinetto, João F Henriques, Jack Valmadre, Philip Torr, and Andrea Vedaldi. Learning feed- forward one-shot learners. In Advances in Neural Information Processing Systems, pp. 523-531, 2016.
307
308
309
Catoni. PAC-Bayesian supervised classification: The thermodynamics of statistical learning. institute of mathematical statistics lecture notes mocnogrph series 56. IMS, Beachwood, OH. MR2483528, 2007.
311
312
Nello Cristianini and John Shawe-Taylor Kernel methods for pattern analysis, volume 173. Cam- bridge University Press Cambridge, 2004.
313
314
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning-to- learn with statistical guarantees. In Proceedings of the Fourth Conference Uncertainty
315
10

---

Under review as a conference paper at ICLR 2020
in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pp. 457-466, 2018a.
317
318
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around common mean. In Advances in Neural Information Processing Systems, pp. 10169-10179, 2018b.
319
320
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-leam stochastic gradient descent with biased regularization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA,
322
324
Pp. 1566-1573 2019.
325
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent PAC-Bayes priors via differential privacy. In Advances in Neural Information Processing Systems, pp. 8430-8441, 2018.
328
327
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1126-1135. JMLR. org, 2017.
328
329
330
Tomer Galanti, Lior Wolf, and Tamir Hazan. A theoretical framework for deep transfer learning. Information and Inference: Journal of the IMA, 5(2):159-2099 2016.
332
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. Pay-bayesian leamn ing of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 353-360. ACM, 2009.
333
334
335
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.
336
Benjamin Guedj. A primer on pac-bayesiar learning. arXiv preprint
2019.
337
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9,
338
329
2015, Conference Track Proceedings, 2015.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16. 2014, Conference Track Proceedings, 2014.
341
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
344
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter PAC-Bayes bounds through distribution-depeedeent priors. Theoretical Computer Science, 473:4-28, 2013.
346
347
Andreas Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research, 6(Ju)):967-99) 2005.
3/9
David A McAllester. PAC-Bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pp. 164-170. ACM, 1999.
350
Thomas Mensink, Jakob Verbeek, Florent Perronnin, and Gabriela Csurka. Distance-based image classification: Generalizing to new classes at near-zero cost. IEEE transactions on pattern anal- ysis and machine intelligence, 35(11):2624-2377 2013.
352
Emilio Harrado-Hernánder Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC-Bayes bounds with data dependent priors. Journal of Machine Learning Research, 13(De)):3507-3531, 2012.
355
356
357
Anastasia Pentina and Christoph Lampert. A PAC-Bayesian bound for lifelong learning. In Inter- national Conference on Machine Learning, pp. 991-999 2014.
Siyuan Qiao, Chenxi Liu, Wei Shen, and Alan L. Yuille. Few-shot image recognition by predicting parameters from activations. In 2018 IEEE Conference on Computer Vision and Pattern Recog- nition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 7229-7238, 2018
380

---

Under review as a conference paper at ICLR 2020
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. In 5th Interna- tional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
363
365
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In Proceedings of the 31th International Con- ference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pp. 1278-1286 1286, 2014.
386
367
388
Omar Rivasplata, Csaba Szepesvari, John S Shawe-Taalor, Emilio Parrado-Hernandez, and Shiliang Sun. PAC-Bayes bounds for stable algorithms with instance-dependent priors. In Advances in Neural Information Processing Systems, pp. 9214 9224, 2018.
370
Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osin- dero, and Raia Hadsell. Meta-learning with latent embedding optimization. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
373
374
375
376
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems, pp. 4077-4087, 2017.
377
378
Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012.
379
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In Advances in neural information processing systems, pp. 3630-3638, 2016.
380
381
Risto Vuorio, Chao-Hua Sun, Hexiang Hu, and Joseph J Lim. Toward multimodal agdel-agnostic meta-learning arXiv preprint arXiv:1812.07172. 2018.
382
Xin Wang, Fisher Yu, Ruth Wang, Trevor Darrell, and Joseph E Gonzalez. Tafe-net: Task-aware feature embeddings for low shot learning. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1831-1844 2019.
384
Flood Sung Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Salt Lake City, UT, USA, 2018.
387
388
389
Kai Yu, Tong Zhang, and Yihong Gong. Nonlinear learning using local coordinate coding. In 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 concept space. arXiv preprint arXiv:1802.03522 2018.
392
393
Luisa M. Zintgraf, Kyriacos Shiarlis, Vitaly Kurin, Katja Hofmann, and Shimon Whiteson. Fast context adaptation via meta-learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 7693-7702,
385
396
2019.
12

---

Under review as a conference paper at ICLR 2020
This supplementary document contains the technical proofs of theoretical results and details of ex- periments. It is structured as follows: Appendix present notations for prior predictor. Appendix B gives the proofs of the main results. Appendix [3.1 and B.2 show the approximation error between I. LCC--ased prior predictor and empirical prior predictor, expected prior predictor, respectvely. They used in the proof of Theorem [ Next, in Appendix [B3 and [B.4] we show the PAC-Bayes gener-
398
400
402
alization bound of localized meta-lcarning in Theorem 3 and also provides the PAC-Bayes general-
403
ization bound regular meta-learning Theorem
2
Finally, details of experiments are presented
404
in Appendix
A
NOTATIONS
Let (+)-) RRd Rdw be the feature embedding function. mik denotes the number of samples belonging to category k. Si and Dit are the sample set and data distribution for category k in task i, respectively. Then, the expected prior predictor w.r.t. class & in task is defined as:
w [k] (D
E
Σ (x(x)).
SumDma
Mil
xyESit
The empirical prior predictor w.r.t. class le in task is defined as:
w < = (Sa))
Σ (x(x)).
X, Xy
The LCC-based prior predictor w.r.t. class l in task i is defined as:
</lk| = (Sax = mik
Σ E
(u(x))
Xj ESu uec
.06
B
THEORETICAL RESULTS
407
B.1
PROOF OF LEMMA
This lemma bounds the error between the empirical prior predictor w/ and the LCC-based prior predictor [k:]
408
409
Lemma Given the definition of w [k] and w/[kk] in Eq. 66) and Eq. 7 let (y, C*) be an arbitrary coordinate coding on Rdd and & be an (a, Lipssciz smooth function and We have for all
E R
| w||lll
Σ (al|x, - X,1l + Σ ||8 (xk]-ul?)
ull)
O0,
(16)
mikk
x, ES
uEC
where x, = =Eucc Yu 7u(x))u Then given any > 0, there exists a coding (7, C) such that
(1 0n, 5 facM (1 + 5V 5/ d
(17)
13

---

Under review as a conference paper at ICLR 2020
Proof. X, Eucc Yu(X))u. We have
[[ - (Si(
1
Σ
[| - Σ Tu((x)
Mik xyESu
uEC
1
Σ
(1g) (x(x))ll2+ Σ Yu(x) -B
mik xyE
uEC
Σ
(xx) - (x,())1122 Σ [x( (Fx()) - -vv( Σ Tx(x)) - (8,( -xy]la)
Mik Sik
uEC
uEC
1
(xx) (x,))11
Σ
Yu (x)) - dv( Σ
(u(x))u)) (u
Mis xyESik
uEC
nEC
Σ
[al|x x;112 +
Σ uEC
|x,
= C)
mik E,ES
410
In the above derivation, the first inequality holds by the triangle inequality. The second equality holds since Euec Tia (x,))) 1 for all xy. The last inequality uses the assumption of (a,, B) L-ipsshciizz smoothness of (-).
According to the Manifold Coding Theorem in Yu et al. 2009,, if the data points x lie on a compact smooth manifold M. Then given any 0, there exists anchor points C' C .M and coding such that
ICI S (1 + (e.
1
Σ (allx, - X + 3
Σ |x3 - ull3) s facm + (1+ (L EEC
(18)
mik
XyESi
413
This implies the desired bound.
414
The first inequality of this lemma demonstrates that the quality of LCC approximation bounded by two terms: the first term ||x X,ll2 indicates should be close to its physical approximation x, the second term |Xx - u implics that the coding should be localized. The second and third inequality show that the approximation error of local coordinate coding depends the intrinsic di- mension of the manifold instead the dimension of input. If set of anchor points C' has cardinality
416
418
O(dMN(e, M)). emprical prior predictor can be linearly approximated using LCC up to accuracy O( (VVdme").
419
B.2
PROOF OF LEMMA 2
422
In order to proof Lemma 2 we first introduce relevant theorem.
Theorem 4. (Vector-valued extension of McDiarmid's inequality (Rivasplata et al., 2018)) Let
X XI...., .......,.... E X be independent random variables, and f X + IR be vector-valued mapping function. If, for all i {I....,m), m.. and for all X1...., Xm x4 E X, the function f satisfies
sup (x Xz, Xi+1sm) - (aami)-j(xxp f(x11-1, X X S Sa x.x
(19)
Then (XIlf(X B[f(X S v E c. For any & E (0, 1) with probability 2 ô we have
m
m x==
2
[5(X -E( 1:m <
Σ
log
(20)
2
423 The above theorem indicates that bounded differences in norm implies the concentration of f(X 1mm) around its mean in norm, i.e., (X (1.m)))))) is small with high probability.
14

---

Under review as a conference paper at ICLR 2020
Then, we bound the enror between expected prior predictor w." and the empirical prior predictor WP.
Lemma 3. Given the definition of w [k] and w [k] in
5 and 66. let X' be compact set with with probability 2 1 ö, we have
radius R, Le., Vx, x' E X, x x' S R. For any E (0,
Iw [k] w [+]]
< aR (1 ++++
log 1
()))
(21)
VmR
Proof. According to the definition of (-) in 66. for all points Xi.... Xj-1, Xj+1. Xma X in the sample set Sik. we have
( (x1:5 X,, Xs+1mm+) i (x1: X33 X/+1mme)]
sup x
R.
sup ( - (x(x)] mik x,
sup al|x; x²y1 1
(22)
misk x,
m7k
where R denotes the domain of say R = supx ||x]] The first inequality follows from the Lipschitz smoothness condition of (.) and the second inequality follows by the definition of domain X. Utilizing Theorem 4 for any ò E (0, 1] with probability 2 1 we have
aR
w !w/[ w/ [[]]] | (Sa:) - El (Sa))l
(1 + Mmix
log g)).
(23)
427
This implies the bound.
Lemma 3 shows that the bounded difference of function (-) implies its concentration, which can
429 he further used to bound the differences between empirical prior predictor w. [k] and expected prior predictor w!" [k]. Now, we bound the error between expected prior predictor w!" and the LCC-based
430
431 prior predictor w..
Lemma 2 Given the definition of w!" and w. in (5) and let A' be compact with radius R, i.e. Vx, x E X, ||x x'11 S R. For any d E (0, 1] with probability 2 1 - ō, we have
K
aR
1 log ())) 00..61..))
Iw w
(1 +
(24)
Mmik
km
Proof According to the definition of wf', w.' and w., we have
111
K
W [k]] w. 2
K
(Sxx) + (S(a) (Saa))
R=1
(1 (S++)] (St))) (1 (2 -S (Q.(()) (.(s
(#v(Sa)
K
[I (Sta)) (S())) (1 -
(25)
Substitute Lemma and Lemma I into the above inequality, we can derive
(1 V log( ( 00. )² 21 1
IP "in | w p
aR /mak
21 (26)
15

---

Under review as a conference paper at ICLR 2020
This gives the assertion.
433
Lemma2 shows that the approximation error between expected prior predictor and LCC-based prior predictor depends the number of samples in each category and the quality of the LCC coding
435
scheme.
B.3 PROOF OF THEOREM 3
Theorem 3 Let Q be the posterior of base learner Q = (N Tiw ouldn) and P be the prior (S), a ddw). The mean of prior is produced by the LCC-based prior predictor (S) in Eq. ( and its parameter v is sampled from the hyperposterior of meta learner Q = N(v2. a ld.)..
Give the hyperprior P = _N(0, Ia, ). then for any hyperposterior Q, any Cı, C1,02 C2 > 0 and any 6 E (0, 1] with probability 2 1 8 we have,
cí 20q
GC C2nemo
er(@) Sc)che(())
Σ
1
|E
1 (S)))l
2cino
4C2
K
aR
(1 +
4n log( σ
)) + O 00.0611C))
2
+ dwkk
Ki (2)2
02 k=
Wmiih
Ow
log 4n
d
+
log
(27)
8
201
where of I-e and
c2 I-e
We can simplify the notation and obtain that
GCb
&
GCL Conm,o
er(2) Sc)eE6 +
202mm;02 + 2cino
)|
11
|EW
-
(S:)l1
+ const(a, 8, m²).
(28)
437
Proof Our proof contains two steps. First, we bound the error within observed tasks due to ob- serving limited number of samples. Then we bound the error on the task environment level due to observing finite number of tasks. Both of the two steps utilize Catoni's classical PAC-Bayes bound (Catoni] (2007) to measure the error. We give here general statement the Catoni's 's classical PAC-Bayes bound.
438
440
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 loss function g(S, x):
X - [0, 1}, and let XG A (X1....;Xc; be a sequence of independent random variables distributed according to X. Let π be some prior distribution over F (which must not depend on the samples (a....,Xk,, For any E (0, 1), the following bounds holds uniformly for all posterior distribution over F (even sample dependent),
G
KL(p)(T) log 17
PXX ad
E E X~XSMp
c
E juu
Xx)
.V0}
1 6
K x
g=1
21-6.
(29)
442
First step We utilize Theorem 3 to bound the generalization eπror in each of the observed tasks. Let E 1,...,7 n be the index of task. For task we substitute the following definition into
443
the Catoni's PAC-Bayes Bound. Specifically, X, & (xiy. Bty), K & m, denote the samples and D, denotes the data distribution. We instantiate the hypotheses with a hierarchical model A (v, w). where v E I& and w E Rdw are the parameters of meta learner (prior predic- tor) (v(+) and base learner h(-) respectively. The loss function only considers the base learner, which is defined o(f,)) & ((hw(x), v). The prior over model parameter is represented A (P, P) & oT,, oZ Ja,)). Gaussian distribution (hyperprior of meta
444
445
446
16

---

Under review as a conference paper at ICLR 2020
learner) centered at 0 and a Gaussian distribution (prior of base leamne) centered at wP, respec- tively. We set the posterior to p a QQ & (N(vv, o. W )), Gaussian dis- tribution (hyperposterior of meta learner) centered at v and a Gaussian distribution (posterior of base learner) centered at wº. According to Theorem 5 the generalization bound holds for any posterior distribution including the one generated in our localized meeanng framework. Specif- ically, we first sample from hyperposterior NVv o..aa)) and estimate w by leveraging pected prior predictor w." (D).). The base learner algorithm As(S, P) utilizes the sample set S and the prior P N(wP, ow law)) to produce a posterior Q As(S, P) = NNw2, (aw.) )-
452
454
456
457
Then we sample base learner parameter w from posterior NVw?, o (ay) and compute the in-
458
459
curred loss (hw (x), y). On the whole, meta-learning algorithm Am (S...... Sn, P) observes
a series of tasks Si..... Sn and adjusts its hyperprior P = N(v?, TTTa) into hyperposterior
460
Q (Si...... Sn, P) = NN(ve of Ja,).
461
The KL divergence term between prior n and posterior p is computed as follows:
(L(pTT) = E log p(f) fmp
N(v2, o. (otta
E v-Niv2,o WwwNNWW ao N(ve,olla))
E'
log NI0, o2 WWWP (alla N(w (wdld)) log N(wP, o Idw)
T(f)
E
log
E vnN ww.Viv www.a, (wW
E
v-N(ve {
o(0,oRla.)
1
1
+
E
1
/w -we-w"l?
(30)
20
v-N(vO
20
In our localized meta-learning framework, in order to make K KL()))P) small, the center of prior distribution w" is generated by the expected prior predictor w" (D). However, the data distribution D is considered unknown and our only insight as to Dia is through the sample set Si-- In this work, we approximate the expected prior predictor (D) with the LCC-based prior predictor w. = (S). Denote the term v-N(ve 2
E
- / w w/|| by T E wPll
20
for convenience, we have
EF 1 2o
Q
w 1
E
w ? w" + wp 111
20
-E
9 wP112 + || w/l1 +2( - WWP) (w. wP)]
v 2
w
<
| 0 wp112 + || - w 111 + 2/ w w/1l
20
E σ v
o Bllwp wP p11 1|2
(31)
Since w.P = =b,(S,) = (Sn (s(a)). (Six))) we have
K
? Q (S.)11
E w 8 [k] - (Sxx)1
[5 [ @gll:?1k [k]] ( (1,
|w ? [k]] 5 (1iu)12++ dn (2)
v
@ee + Ko
(32)
17

---

Under review as a conference paper at ICLR 2020
where (Sa)ll denotes the variance of (S The last equality uses the fact that dy
[Cldw. Combining Lemma 2 for any 8' E (0. 1] with probability - 8' we have
1
Iw;
w!'
v 20 w
2
1
Ew;
2
Tee + d K( Ov
)²
)²+
1
Σ
aR
1 (1 + V log( ())) O 02 C)
ow
Ow
ow
mmisk
km1
(33)
Then, according Theorem
we obtain that for any 4 > 0
P
E(ww (x),
D.v WwW(W
(w Tawe)
02
1
m4
E NnN(vVO,220
E Www.Nw/.ll......
((hw ((w((x)), (x)), Ug)
1 e
mi
j=1
8,
+
| 12
E v~N( WW
w -w!ll + log
SQ
2
(1 -=)) mi
20
20
2
(34)
d for all observed tasks I,...,m.. n. Define 8' and combine inequality 33 we obtain
E Viv B W~N(W9 law) C(hw (x),
E
E
((hw(x), y)
mi
E
e(h (x;); Ms)
mi
v.vi(v ozda, o Www. (a
+
1 +
1
Ew - @ve(iill? + log 8,
2
+ d dwk( (r)
(1 - 1----)m mm
20
o
Ow
K
aR
I
2 )) +
000() ve 11 S,.
(1+
log(
(35)
Vmik
0
Using the notations in Section 4 the above bound can be simplified as
P PS
aa (A(o(S,,,P))
C2
<
er (Ab(Si, P.))
e 12
v-Niive
+
1
1
+
1
tve (5:)112 + +lo IE
2
+ d K( K(
Jrzz
--
20
6,
Ow
K
aR
(aa(()))))) 2 8,
2 )) +
ve .v0 1-8 8z.
log
(36)
2
Mikk
km
Second step Next we bound the eтrоr due to observing limited number of tasks from the envi- ronment. We reuse Theorem with the following substitutions. The samples are mD, S,), = 1,...,n, where (D,, are sampled from the same meta distribution 7 and S; ~ D The hyposthesis is parameterized as (D) with meta learner parameter v. The loss function is WWW.D--WWW9,,,.... E(hw (x), y). where & = As, P.). Let क & NO, of be
g( e E
18

---

Under review as a conference paper at ICLR 2020
the prior over meta learner parameter, the following holds for any 60 0,
E(hw (x), y)
[D, (N,,i,D
(
Jaw Dr
5
C1
E
Now (2, e(hw(x),))
n
v~Nive 00 (a w WwwNWwwwee (WW.(WWWggg
1
2
log 60
10 2 60.
(37)
- e y
2
Using the term in Section
4 the above bound can be simplified
i er(2)
E V ( P. cr(Ac(S,, P.))
1 1 log 50
v4 vo]=
21 50:
(38)
0 n
2
Finally, by employing the union bound, we could bound the probability of the intersection of the
events 36 and 380 For any 8 > O, set &o & g and 6, - 2n for = I,..., n, we have
P PDD" ii er(@)
C002
E PI
Jaw (Ab(,S P.))
(1 e e1-ea)(( [1 e
-2) n
(rV (D N( Jaw)
C1
1
1
1
Ew? (e))ll1 + log
4n
5
(1-e-c))m,
20
o
8
i=1
K
aR
(1+ 2 log( 5ラ + Oa.s(T:C))
- dw =2)
Mikk
Fw
k=1
11 + log 2 10 2 21
+
+lo
(39)
(1-e-c1)m )n
We further simplify the notation and obtain that
S (G P (NT,S""" i=l... er(()ss
c/ch
di
n 11121122
c/
|Ew vve
2
2c1noz
conmo
+const(a, B, R, R, n. m.), YQ
> 1 1-
(40)
where of T-e and ce -T-
This completes the proof.
B.4 PROOF OF THEOREM 2
Theorem 2 Let Q be the posterior of base leamner Q NWWwe,0 and P be the prior N(w o I The mean of prior is sampled from the hyperposterior of meta learner Q
N(we o Id Give the hyperprior P = NN(0, of Ta,)) then for any hyperposterior Q, any
19

---

Under review as a conference paper at ICLR 2020
C2 > 0 and any 8 (0, 1] with probability 2 1 8 we have,
dic
d
er(@) SGGEr(()
+
+
)|w
E w W
w212
2
20 no
20yn
:=1
w
w
GP2 mm
1
2n
ci
2
log
log
(41)
8
cino
w
484
where of T-e-oy and c2 T-e-12
Proof Instead of generating the mean of prior with prior predictor, the vanilla meta-learning framework directly produces the mean of prior w by sampling from hyperposterior Q N(w ww ! Then the base learner algorithm As P) utilizes the sample set S and the prior P = N N(w" o. Id to produce posterior Q = P) = =N(w9, o la.)) Similarly with the
two-steps proof Theorem 3 we first get an intra-task bound by using Theorem 5
For any 8; 0.
we have
P D.
E (x.y)~D.wf WWW Jaw Jaw WwW/ of Jaw)
((hw(x), v)
my
C2
E(hw (Xy).
1 - c
m
w NWWNNWW, oz wwwN law)
j=1
|| 2
E w! wf'>N NN
1
I|??
-w. w/Pl1
+ log
5, vQ
1
2 1 - 8,
(1 0=)2) mm
20
oz Naw
20
(42)
The term
20 !
w/ll can be simplified as
w/-NNWW.,t o law
E
l|w? w/
w. N
.02 Jaw
20 w
E w Q 913 - 2( E w T) T + +1|w
v [l/l//]] w
20
w.
[| ? w 11 + 02
(43)
20 w
w
where V [[] denotes the variance of ||w
Then we get an inter-task bound. For any 50 > O.
we have
P. >rTSSr""""""" jmlm.. (D
E
E
E E(hw (x),
NN "n Now o0 ol anw wwW (e
E
E
E (x),
e
n iml
wp ( /a
/ www.Wwww . ar Naw (0..0))~ Dr.
1
1
_v0
w 012
log
1- 50-
(44)
'n
202
50
20

---

Under review as a conference paper at ICLR 2020
For any 8 > O, set 60 and 6, - 6 for i 1.... Using the union bound, finally get
P P(DD" P(D (.. i
er())
R
(r(A(SS P.))
1 - 1-
12
n
( kw
n
1
1
2n
|
112 +
E
w
w111 + + log
0 -
(1 - 0-)
m
2
20
W.
2
8
|
log
8)
S4
2 1 8.
(45)
(1- (1--a)m
20
Similarly, we can further simplify the notation and obtain that
(i er (r(()) S (
P )rr""""
d
E w
- w
1=1
20ynm;o
20
w
202mm;
2
w
+const n, mi), v0
2 1-
(46)
485
where e T---o and cg ---
This completes the proof.
C DETAILS OF EXPERIMENTS
467
C.I
DATA PREPARATION
468
We used the 5-way 50-shot classification setups, where each task instance involves classifying im- ages from 5 different categories sampled randomly from one of the meta-sets. We did not employ any data augmentation or feature averaging during meta-training, or any other data apart from the corresponding training and validation meta-sets.
469
470
472
C.2
NETWORK ARCHITECHTURE
473
Auto-Encoder for LCC For CIFARI00, the encoder 7 layers with 16-32-64-66--18--12--22
channels. Each convolutional layer is followed by a LeakyReLU activation and a batch normaliza- tion layer. The 1st, 3rd and 5th layer have stride and kernel size (3, (3. The 2nd, 4th and 6th layer have stride 2 and kernel size (4, 4). The 7th layer has stride and kernel size (4, 4). The decoder is the same as encoder except that the layers are in reverse order. The input is resized to 32 x 32. For Caltech-256, the encoder is layers with 32-64- 1754-128--555 12-2256-256 channels. Each convolutional layer is followed by LeakyReLU activation and a batch normalization layer. The first 4 layers have stride 2 and kernel size (4, 4). The last layer has stride and kernel size (6, 6). The decoder is the same as encoder except that the layers are in reverse order. The input is resized to 96 x 96.
475
477
479
480
482
Base Model The network architecture used for the classification task is small CNN with 4 con- volutional layers, each with 32 filters, and linear output layer, similar to (Finn et al. 2017). Each convolutional layer followed by a Batch Normalization layer, a Leaky ReLU layer, and a max- pooling layer. For CIFAR 100, the input is resized to 32 x 32. For Caltech-256, the input is resized
484
486
to 96 x 96.
487
C.3
OPTIMIZATION
Auto-Encoder for LCC As optimizer used Adam AdamaKingma & Ba 2015 with B1 0.9 and
32 = 0.999. The initial learning rate is 1 x 10-4, The number of epochs 100. The batch size is
489
512.
21

---

Under review as a conference paper at ICLR 2020
LCC Training We alternatively train the coefficients and bases of LCC with Adam with A1 = 0.9 492 and 82 = 0.999. In specifics, for both datasets, we alternatiely update the coefficients for 60 times and then update the bases for 60 times. The number of training epochs is 3.The number of bases is 64. The batch size is 256.
494
Pre- Training of Feature Extractor We use 64-way classification in CIFAR-100 and 150-way classification Caltech-256 to pre-train the feature embedding only on the meta-training dataset.
496
487
For both CIFARI00 and Caltech-256, an L2 regularization term of 5e 54 was used. We used the Adam optimizer. The initial learning rate is 1 x 10-3, 31 is 0.9 and 82 is 0.999. The number of epochs is 50. The batch size 512.
488
499
500
Meta- Training We use the cross- cossopy loss as in (Amit & Meir 2018). Although this is inconsis-
501
tent with the bounded loss setting our theoretical framework, we can still have guarantee on variation of the loss which is clipped to [0. 1]. In practice, the loss is almost always smaller than one.
502
503
For CIFAR 100 and Caltech- the number of epochs of meta-training phase is 12; the number of epochs of meta-testing phase is 40. The batch size is 32 for both datasets. As optimizer we used Adam with 31 = 0.9 and 32 = 0.999. the setting with a pre-trained base model, the learning rate is 1 x 10-5 for convolutional layers and 5 x 10 for the linear output layer. In the setting without pre-trained trained base model, the learning rate is 1 10 3 for convolutional layers and 5 x 10 for the linear output layer. The confidence parameter is chosen to be 8 = 0.1. The variance hyper-paramenn parameter for prior predictor and base model are dw Bv = 0.01. The hyperparameter 01 02 in LML and MI-A set to 0.01. For MAML (Finn al. (017) and MatchingNet (Vinyals et al. 2016). Both two methods use the Adam optimizer with initial learning rate 0.0001. In the meta-training phase,
505
507
a pre-
509
511
512
we randomly split the samples of each class into support set (5 samples) and query (45 samples).
513
The number of epochs is 100. For MAML, the learning rate of inner update is 0.01.
22


Reviews:
[{"review_id": "rkeqdjJOcS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI would like to accept this paper. It has very clear contributions to meta-learning. I expect the core idea of splitting a single hyper-prior into anchor-points to have good impact on real problems because the task diversity in most realistic meta-learning scenarios makes it difficult to learn a meaningful hyper-prior.\n\nI have a few minor comments which I would like the authors to address.\n\n1. Choosing the prior w^P using data from the new task will work well if one has access to a few support samples. How do your experiments reflect this? I think the numerical results in Figure 3-4 are high because the shot is abnormally high (it is 50). It is possible to simply fine-tine a pre-trained network to near perfect accuracy with this much data. This is a major drawback of the predictor for the prior.\n2. Can you show results for more standard settings, e.g., 5-way, 5-shot? Can you show results on mini-ImageNet?\n3. One way to build upon Theorem 2 would be to use the generalization error of the predictor Phi_{v^Q}(S) and characterize the number of support samples one necessary for a given number of anchor points.\n4. The authors note in Section 5.1 that the meta-learning objective is difficult to optimize. It is unsatisfying to use the pre-trained model as an initialization for the meta-training. Can you elaborate more on this?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SyeChbnu5S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n​\nThis paper proposes a tight bound in generalization to new tasks in meta-learning framework, by controlling the task prior with Local Coordinate Coding (LCC) prediction. In classification tasks, the algorithm using this bound demonstrates superior performance over other meta-learning methods which are based on PAC-Bayes bounds, but without the proposed prior prediction. \n​\n​\n### Strengths\n- The paper is well written, and maintains a logical flow with the proofs and inference from them.\n- The idea and intuition for using a learned prior is sound, and is backed by PAC-Bayes theory.\n- Proposing a tighter generalization bound O(1/m) as opposed to existing bounds of O(1/sqrt(m)) is a meaningful contribution and its efficacy is well shown in the results.\n​\n### Weaknesses\n- Could the authors comment on how their LCC-basedd prior prediction can be extended to other meta learning setups like regression and reinforcement learning?\n- The baselines compared with are other PAC-Bayes bounds and successfully justifies the contribution. Could the authors provide a comparison with other meta-learning methods (like [1]) to have a holistic view of where this proposed bound gets this line of work?\n​\n​\n#### Minor:\n- Spellings: \"pratical\" -> \"practical\" (pg1, abstract); \"varible\" -> \"variable\" (pg 3); \"simplifies\" -> \"simplify\" (pg6, optimization of LLC)\n- [2] seems to be a related work, as instead of using the global prior, they identify the task first (similar to localized prior), and then utilize it for better performance.\n​\n### References\n[1] Finn, Chelsea, Pieter Abbeel, and Sergey Levine. \"Model-agnostic meta-learning for fast adaptation of deep networks.\" Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.\n​\n[2] Vuorio, R., Sun, S. H., Hu, H., & Lim, J. J. (2018). Toward multimodal model-agnostic meta-learning. arXiv preprint arXiv:1812.07172.\n​\n​\n### Score\n6 - Weak Accept", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1gb7pTV5B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work, the authors introduce PAC-Bayesian generalization bounds for Meta-Learning. In their framework, they have a hyper-prior distribution, a class of hyper-posteriors and an algorithm A that takes a sample set Si from task Di and a prior P and returns a posterior Q. \n\nPros:\n-- Overall, the main text of the paper is finely written.\n-- The motivation is well articulated.\n-- The relationship with local coordinate coding seems like an interesting direction.\n-- The experiments seem sensible. \n\nThe novelty of the bound in Thm. 1:\n-- It seems that several aspects of the high-level derivation methodology of the bound are not new. Instead of applying McAllester’s bound twice (as done by Galanti et al. 2016, Amit and Meir 2018), the authors employ Catoni’s bound (a different variant of PAC-Bayes) twice. In addition, the authors apply the standard Gaussian randomization which leads to L2 regularization terms as the capacity terms -- also well known in the literature (see for example Hazan et al. 2013, etc’). \n-- I would be happy if the authors point out which parts of their derivations are novel, for instance, the application of local coordinate coding, etc'.\n\nI think the authors' claim that their bound (Thm. 1) is tighter than previously existing bounds is a bit questionable:\n-- There are already PAC-Bayesian bounds with the proposed orders of magnitudes with the exact same coefficients by Catoni 2007 and Pascal Germain et al. 2009. In fact, the authors employ Catoni’s bound within the appendix. In my opinion, it should be addressed in the main text. \n\n-- In addition, their bound has two coefficients that are being ignored in their analysis of its magnitude: c/(1-exp(-c)) (here, c stands for c1 or c2) for the error term and 1/(1-exp(-c)) for the capacity term and an additional constant that depends on n,mi and \\delta. In the previous bounds, the coefficients are 1 for the error term and 1 for the capacity terms. I think the paper would greatly benefit from a direct comparison between the two.\n\nFor instance, as a direct comparison between the two bounds, I would select c, such that, 1/(1-exp(-c)) is close to 1. However, in this case, the coefficient 1/(1-exp(-c)) of the capacity term is huge and makes the overall capacity term very large, which is not favorable. Therefore, it seems to me that the proposed bound is favorable only when the training error is very small (realizable case) and c can be selected to be large. However, when the training error is assumed to be small, it is well known that the gap between the generalization risk and the empirical risk is of order O(capacity/m) (see Thm. 6.8 (bullet 3) in S. Shalev-Schwarz and S. Ben-David 2014). Again, this is also a property of the original bound by Catoni.\n\nFinally, the authors mention that the parameters c1 and c2 control the tradeoff between the empirical error and the capacity terms. I think this is a bit inaccurate, since, c1 and c2 are selected a-priori to the estimation of the error term. Therefore, should be independent of the error term. \n\n-- The presented bound has an additional constant “E_i[const(n,mi,delta)]”. \nIt is unclear to me what is the magnitude of this quantity. I think it might improve the paper if the authors explicitly analyze this term.\nFrom the proof of Thm. 2 (Eq. 36) it seems to be of order >= ( O_{\\alpha,\\beta}(\\gamma,C) + (1/m_{ik})^{1/2} )^2. \nWhat is the definition of m_{ik} (couldn’t find it, maybe it was defined somewhere -- I think it should have been recalled)? I’m assuming it is mi or something similar. \nSecond, I’m not sure how to estimate the size of O_{\\alpha,\\beta}(\\gamma,C). From Lem. 1 it depends on some arbitrarily selected quantity \\epsilon > 0 and |C| is a function of \\epsilon, so I’m not sure how to measure it. \n------------------------------------\nSoundness: \nThere are a few things that I'd be happy if clarified regarding Thms. 1 and  2. \n-- I’m not sure what is w^Q_i (couldn’t find its definition anywhere). I guess w^Q_i is the center of Q_i = A(Si,P), where P ~ \\mathcal{Q}. How can w^Q_i be free within the inequality without being bound to an expectation over P? Especially since you take an expectation over P within the training error. I guess the correct formulation of the bound is one that has  E_{P ~ \\mathcal{Q}}[||w^Q_i - w^{\\mathcal{Q}}||^2] instead of ||w^Q_i - w^{\\mathcal{Q}}||^2. \nMaybe the issue is somewhere in between Eq 39 and 40, where the authors take an expectation over Pi (which is not clearly defined as well), but not over Qi?\n-- In Eq. 27 last equality: we have a term of the form: E_v ||w^Q - w^P||^2. Where is v in the distance squared?\n-- I’m not sure what is the motivation of applying Eq. 28, the bound should be tighter with the LHS term instead of the RHS.\n-- In the top half of page 15, P stands for a prior independent of \\mathcal{Q}, while in the main text, P~\\mathcal{Q}. Therefore, the relationships between different arguments are unclear to me.   \n-- Finally, I think the paper could be improved if the authors would organize the appendix.\n\n\nExperiments:\nIn your experiments you compare the derived algorithm to other PAC-Bayesian baselines. Can you show that your algorithm outperforms other existing baselines in the literature of Meta-Learning (in terms of generalization, etc')?\n\nTypos:\n-- “Catino” ---> “Catoni”.\n\nFinally, I think the authors should address the public comment by Tomer Galanti. It seems that Thm. 9 in Galanti et al. (2016) introduces a PAC-Bayesian theorem for Meta-Learning (they call it transfer learning), similar in its nature to Thm. 1 in the current paper. In Thm. 9 they have a hyperprior, denoted by P, learn a hyper posterior Q, for selecting posteriors qi for many different tasks di. In their framework, for each task di, their method returns a posterior qi that minimizes the bound for a specific task. This distribution, qi, is a function of a prior B selected by Q (P in your notation) and the i’th task’s dataset si (Si in your notation). Therefore, instead of denoting it by A(Si,P) as done by the authors, they simply call it a minimizer (but it is a function of the same argument that the authors address). Overall, it seems to me that Galanti et al. had a very similar setting, with different notations and focus on a specific algorithm A. \n\n\nI think that overall, the paper has interesting insights and the relationship with local coordinate coding seems like an interesting direction. However, I think the paper should not be published in its current form. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJelocwZ5H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post-rebuttal:\n===========\nThank you to the authors for responding to my review, and for adding the comparison to other meta-learning methods besides Amit et al. (2018), which makes it clearer in which settings this technique outperforms purely discriminative approaches (in particular with few tasks & many samples from each task). However, I would assume that not using support-query partitioning for MAML and Matching Nets is likely to reduce their performance.\n\n> \"Second, from the algorithm perspective, we use the whole sample set S as the input for LCC-based prior predictor \\bar{w}^P = \\bar{\\Phi}_v(S) .\"\nThanks to the authors for this clarification--it is now clear to me that the experimental setup is not the episodic training setup of Vinyals et al. (2016) that partitions episodes into support and query sets, thus the difficulty of comparison to other few-shot learning methods that use this setup.\n\nHowever, this exposes a potential problem with the formulation: As the authors state in the submission, \"...the prior P_i in each task has to be chosen independently of the sample set S_i\", in alignment with prior works in data-dependent PAC-Bayes bounds [Catoni, 2007; Parrado-Hernandez et al., 2012; Dziugaite & Roy, 2018]. However, even though the authors begin section 4.1 by stating \"Fortunately, the PAC-Bayes theorem allows us to choose prior upon the data distribution D_i. Therefore, we propose a prior predictor...which receives task data distribution Dm and outputs the mean of prior wP\"; the prior predictor employed is the \"empirical prior predictor\" that operates directly on the sample set S_i.\n\nThis appears to be a contradiction that is not sufificiently addressed in the text (nor in the response to Reviewer #4). To fix this, the authors would have to more clearly explain why their theoretical results do not require the separation of task-specific data into a subset of data used to produce the prior and a subset used in the computation of the bound, or adapt the experimental setting to meet this theoretical requirement (in which case the setup is very similar to the support-query partitioning commonly used to evaluate few-shot learning methods, therefore bringing into question the necessity of using an alternate evaluation protocol to the one that is standard in few-shot learning).\n\nBefore rebuttal:\n=============\nThe submission makes use of a data-dependent PAC-Bayes bound on the generalization error of a classifier estimated in a few-shot learning setup. The episodic few-shot learning setup from Vinyals et al. (2016) provides a small dataset for each task, partitioned into a support and a query set; at test time, only the labels for the support set are provided. The submission takes advantage of this setup by leveraging the support set in the construction of a data-dependent prior, an idea referred to as \"locality\"; this is in contrast to prior work in PAC-Bayes for hierarchical models (e.g., Pentina & Lampert, 2014; Amit & Meir, 2018) in which the data-dependency enters only across tasks, and not within a task.\n\nStrengths:\n- Coherent formulation of data-dependent PAC-Bayes for a meta-learning setting that partitions episodic data into a support set (used to compute the data-dependent prior) and a query set (used to produce the posterior.\n- The method outperforms prior approaches constructed from PAC-Bayes generalization bounds (LML; ML-A; ML-AM; ML-PL) on the Caltech-256 and CIFAR-100 datasets.\n\nWeaknesses:\n- The framing as \"localized meta-learning\" obscures the lack of difference from the standard partitioning in few-shot episodes in a support and query set.\n- The proposed method makes heavy use of prior machinery (LCC, prototype-based prior predictor), and as such, the algorithmic novelty is limited.\n- No comparison is made to approaches that are not constructed use PAC-Bayes generalization bounds (Vinyals et a. 2016; Finn et al. 2017), even though they are readily applied in such settings.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes PAC-Bayes bounds for meta-learning. The reviewers who are most knowledgeable about the subject and who read the paper most closely brought up several concerns regarding novelty (especially a description of how the proposed bounds relate to those in prior works (Pentina el al. (2014), Galanti et al. (2016) and Amit and Meir (2018))) and regarding clarity. The reviewers found theoretical analysis and proofs hard to follow. For these reasons, the paper isn't ready for publication at this time. See the reviewer's comments for details.
Decision: Reject