Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: ### Summary
​
This 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. 
​
​
### Strengths
- The paper is well written, and maintains a logical flow with the proofs and inference from them.
- The idea and intuition for using a learned prior is sound, and is backed by PAC-Bayes theory.
- 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.
​
### Weaknesses
- Could the authors comment on how their LCC-basedd prior prediction can be extended to other meta learning setups like regression and reinforcement learning?
- 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?
​
​
#### Minor:
- Spellings: "pratical" -> "practical" (pg1, abstract); "varible" -> "variable" (pg 3); "simplifies" -> "simplify" (pg6, optimization of LLC)
- [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.
​
### References
[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.
​
[2] Vuorio, R., Sun, S. H., Hu, H., & Lim, J. J. (2018). Toward multimodal model-agnostic meta-learning. arXiv preprint arXiv:1812.07172.
​
​
### Score
6 - Weak Accept
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: 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.

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

I have a few minor comments which I would like the authors to address.

1. 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.
2. Can you show results for more standard settings, e.g., 5-way, 5-shot? Can you show results on mini-ImageNet?
3. 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.
4. 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?
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 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. 

Pros:
-- Overall, the main text of the paper is finely written.
-- The motivation is well articulated.
-- The relationship with local coordinate coding seems like an interesting direction.
-- The experiments seem sensible. 

The novelty of the bound in Thm. 1:
-- 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’). 
-- 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'.

I think the authors' claim that their bound (Thm. 1) is tighter than previously existing bounds is a bit questionable:
-- 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. 

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

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

Finally, 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. 

-- The presented bound has an additional constant “E_i[const(n,mi,delta)]”. 
It 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.
From the proof of Thm. 2 (Eq. 36) it seems to be of order >= ( O_{\alpha,\beta}(\gamma,C) + (1/m_{ik})^{1/2} )^2. 
What 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. 
Second, 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. 
------------------------------------
Soundness: 
There are a few things that I'd be happy if clarified regarding Thms. 1 and  2. 
-- 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. 
Maybe 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?
-- 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?
-- 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.
-- 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.   
-- Finally, I think the paper could be improved if the authors would organize the appendix.


Experiments:
In 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')?

Typos:
-- “Catino” ---> “Catoni”.

Finally, 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. 


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

review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: Post-rebuttal:
===========
Thank you to the authors for responding to my review, and for adding the comparison to other meta-learning methods besides Amit et al. (2018), which makes it clearer in which settings this technique outperforms purely discriminative approaches (in particular with few tasks & many samples from each task). However, I would assume that not using support-query partitioning for MAML and Matching Nets is likely to reduce their performance.

> "Second, from the algorithm perspective, we use the whole sample set S as the input for LCC-based prior predictor \bar{w}^P = \bar{\Phi}_v(S) ."
Thanks to the authors for this clarification--it is now clear to me that the experimental setup is not the episodic training setup of Vinyals et al. (2016) that partitions episodes into support and query sets, thus the difficulty of comparison to other few-shot learning methods that use this setup.

However, this exposes a potential problem with the formulation: As the authors state in the submission, "...the prior P_i in each task has to be chosen independently of the sample set S_i", in alignment with prior works in data-dependent PAC-Bayes bounds [Catoni, 2007; Parrado-Hernandez et al., 2012; Dziugaite & Roy, 2018]. However, even though the authors begin section 4.1 by stating "Fortunately, the PAC-Bayes theorem allows us to choose prior upon the data distribution D_i. Therefore, we propose a prior predictor...which receives task data distribution Dm and outputs the mean of prior wP"; the prior predictor employed is the "empirical prior predictor" that operates directly on the sample set S_i.

This appears to be a contradiction that is not sufificiently addressed in the text (nor in the response to Reviewer #4). To fix this, the authors would have to more clearly explain why their theoretical results do not require the separation of task-specific data into a subset of data used to produce the prior and a subset used in the computation of the bound, or adapt the experimental setting to meet this theoretical requirement (in which case the setup is very similar to the support-query partitioning commonly used to evaluate few-shot learning methods, therefore bringing into question the necessity of using an alternate evaluation protocol to the one that is standard in few-shot learning).

Before rebuttal:
=============
The submission makes use of a data-dependent PAC-Bayes bound on the generalization error of a classifier estimated in a few-shot learning setup. The episodic few-shot learning setup from Vinyals et al. (2016) provides a small dataset for each task, partitioned into a support and a query set; at test time, only the labels for the support set are provided. The submission takes advantage of this setup by leveraging the support set in the construction of a data-dependent prior, an idea referred to as "locality"; this is in contrast to prior work in PAC-Bayes for hierarchical models (e.g., Pentina & Lampert, 2014; Amit & Meir, 2018) in which the data-dependency enters only across tasks, and not within a task.

Strengths:
- Coherent formulation of data-dependent PAC-Bayes for a meta-learning setting that partitions episodic data into a support set (used to compute the data-dependent prior) and a query set (used to produce the posterior.
- The method outperforms prior approaches constructed from PAC-Bayes generalization bounds (LML; ML-A; ML-AM; ML-PL) on the Caltech-256 and CIFAR-100 datasets.

Weaknesses:
- The framing as "localized meta-learning" obscures the lack of difference from the standard partitioning in few-shot episodes in a support and query set.
- The proposed method makes heavy use of prior machinery (LCC, prototype-based prior predictor), and as such, the algorithmic novelty is limited.
- No comparison is made to approaches that are not constructed use PAC-Bayes generalization bounds (Vinyals et a. 2016; Finn et al. 2017), even though they are readily applied in such settings.
review_title: Official Blind Review #1

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