Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Existing meta-learning techniques assume that the number of samples for teach task are drawn from the same distribution.  Theorem 3 shows that a naive decoupling of the number of samples introduces a term to the gap that penalizes additional samples.  The paper bypasses this issue by introducing a fix-sized subset that is used to train a base model.  The additional samples are then used to evaluate the empirical risk, thus removing the aforementioned unsatisfactory term.  The MAML and Reptile algorithms are recovered by considering the derived bound and normal priors along with both delta posteriors (ie MAP solutions) and normal posteriors.  Results are reported on synthetic regression, image classification, and product review classification.
main_review: ### Positives

While I am not an expert in meta-learning or PAC-Bayes, this work seems well motivated (fixing the issue of uniformity in the sample sizes of previous PAC bounds), well executed / technically correct, and novel.  


### Negatives

I was confused a bit by the experimental section.  I thought that the paper would experimentally validate the derived bound, comparing it not only to the empirical generalization error but also the bounds previously derived for meta-learning.  This is done for the synthetic data in Figure 1 but no where else.  Why aren't the bounds empirically studied?
limitations_and_societal_impact: There are no negative societal implications.  The major limitations are identified in the text: "One major limitation of the work is that we do not take into account a data domain shift (e.g. [11]), which is often present in practice."
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Previous PAC-Bayesian Meta-learning bounds assume the number of samples per task follows the same distribution in the meta-training and in meta-testing.  This paper relaxes this assumption, allowing for a shift in the number-of-samples distribution from meta-training to meta-testing (Thm 3).
In Thm 4, the paper suggests a learning strategy that omits the extra distribution shift of Thm 3, by using a smaller data set. 
The paper shows how the popular meta-learning algorithms, Reptile, and MAML can be justified using the PAC-Bayes framework, and also introduces a new algorithm called PACMAML.  Experimental results show the method outperforms other algorithms on several few-shot benchmarks.
main_review: 
Strengths
- The paper is well written. The structure is logical and easy to follow.
- Interesting observation from theory - tighter meta-test bound can sometimes be achieved if the base learner uses FEWER samples  (the same number of samples as in meta-training), this seems counter-intuitive, but helps to mitigate the distributional shift in the distribution over the number of samples.
- Experimental results show the suggested algorithm has favorable performance in few-shot tasks.
**************************************************************
Weakness
- There is an issue that is not addressed. The empirical error increases if fewer samples are used (since we have a base-learner that was trained with fewer samples).  Is it ensured that this increase does not negate the reduction in the complexity term? The paper does not seem to discuss this issue.
-The derivation of the gradient estimators is not clear. For example: (1) below line 602 in the appendix, there is an inequality, but the final result is equality. (2) I couldn’t understand the transitions below line 603.
- The sampling from the distribution $Q(w, S)$ is not trivial (since it involves an exponent of the empirical loss). However, the paper doesn’t elaborate on the sampling method used besides referencing SGLD and SVGD. Since there are only approximated methods for sampling, with advantages and disadvantages, I believe this part should be investigated more in-depth. Furthermore, there is no pseudocode of the full algorithm, and so readers can not recarate the results.  
**************************************************************
Questions
- Line 317 - “the base-learner is only trained on S’ and the meta-learner can learn from the unseen examples in S and therefore no overfitting happens”. This sentence is not clear. How is it guaranteed that there is no overfitting?
**************************************************************
Minor comments: 
- Line 88 - possible typo -  $S_i \sim D$ instead of  $S_i \in D$
- Line 130 - \tilde{T} is undefined
- Lines 137-138 are not clear.
- Line 225, I think REINFORCE is not the name of the method used since it usually uses the log-derivative trick.
- Figure 2 lacks error bars.

limitations_and_societal_impact: The limitations are discussed in the main review. There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the Few-shot meta-learning setting according to PAC-Bayes theory. The authors focus on a context where the number of examples from source tasks and the target ones do not follow the same distribution. The authors develop two PAC-Bayes bounds tailored for the few-shot learning setting. Additionally, two existing and famous few-shot learning algorithms (MAML and Reptile) can be derived from the proposed bounds. 
In that sense, the work aims at reducing the gap between theory and practice by proposing a theory that can justify some existing and efficient algorithms. A new algorithm is also derived from the proposed framework PACMAML. An experimental evaluation on a synthetic problem and on existing benchmarks is presented.
main_review: Originality
-------- 
Understanding few-shot learning methods is still challenging and this work participates to a better understanding of this framework, which represents an important value. 
Existing PAC-Bayesian settings for few-shot/meta-learning do not handle the difference in terms of training size between source and target tasks, so there is a novel aspect here that has the advantage to be more realistic for the few-shot learning setting.
Another property of the framework is to allow to interpret MAML and REPTILE, which also new and offers some justification for these two algorithms, even though this may benefit from more discussion.
An algorithm is derived, using a base strategy borrowed from the PACOH paper, anyway a specific novel formulation is derived.

Overall, the novelty of the paper is rather fair.


Quality 
------
The results are solid and well justified. All claims are justified by proofs and derivations, sometimes included in the Appendix.
The experimental evaluation is rather large and solid.


Clarity
------
The paper is globally clear and convincing.
I had a problem for interpreting the term $\Delta_\lambda$ in Thm3, I would appreciate if the authors can comment more on it.
Maybe the assumptions on T and \hat{T} could be more precisely discussed to avoid any misunderstanding.

Significance
----------
I think that the paper provides a significant contribution for studying the few-shot learning in PAC-Bayes, mainly in three aspects: (i) a framework that takes into account the different sizes between observed and target tasks, (ii) the capacity of the framework to allow an interpretation of two existing algorithms, (iii) the derivation of a new algorithm that provides better results in comparison to other approaches ) related to Pac-Bayes though.

The significance outside the PAC-Bayesian community is not clear but at least the work contributes to the understanding of few-short problem which is important.

Some methodological aspects and results could be more discussed anyway.


Comments
-----------

-line 130: Definition and differences of $T$ and $\tilde{T}$ should require a bit more precision on the expected differences in terms of tasks environment. Is it just that the samples are draws with less examples, or can we imagine more (structural) differences?
According to assumptions of Thm3, line 132/133, if I understood correctly, the environment can output the same distributions, so in other words, the same tasks, but the difference is that in T the expected number of observed samples is smaller.

line 136: I am not sure to understand/interpret correctly the $\Delta_\lambda$ term. From the hypothesis of line 132/133, I understand that the 2 environments provide the same tasks, in expectation, so I would have appreciated more precision in order to explain  why $R(P,T)-R(P,\tilde{T})$ should not be 0 in expectation? One explanation coud that the tasks weights are different between the two environnements (related to my question above but this probably not the case), but my interpretation is that when using smaller samples the base algorithms would produce less powerful base classifiers which cannot be compensated by the posterior, but I may have  wrongly interpreted the notation. I would appreciate if the authors could comment on it.

line 137, first equation: you expect that the number of instances samples in the observed tasks tends to the observed harmonic mean?

-Table 1: the results seem to correspond to accuracy and not generalization error (since the true error cannot be estimated anyway), same for Table2.

-Fig 2, line 279. The U-shaped can indeed shows the beginning of an overfitting situation where the learners starts overfitting on the source tasks. That being said, this could be explained by the fact that the base learners are not chosen, parameterized or regularized correctly for the problem considered. This may indicates that some information are still missing in the proposed bound.

-The analysis of the generalization bounds is deferred to Appendix with the conclusion that PACMAML exhibits better generalization bound than the competitor PACOH in the context of the synthetic experiments. I would be interested in knowing the bounds for MAML or REPTILE for example, to see if the bounds can be informative to perform algorithm selection for some problems. Note also that showing bounds for the other tasks is interesting.

-The bounds provides PAC-Bayesian guarantees and allows to deduce some algorithms, which is good. Maybe something that is missing is to have some information about a structure on the posterior, for example maybe some diversity should be observed on the base learners and when this occurs maybe the guarantees can be better. Maybe extensions that would incorporate such a property would be interested.

-For PACMAML, a particular formulation of the Gibbs posterior is used. This is expected since otherwise one cannot expect to have a tractable approach. However, I would expect a little discussion on the expressiveness of this choice and maybe some possible other alternatives. 

In practice a Monte-Carlo sampling is used, but this implies probably high computational costs, what happened on existing image and natural language benchmarks?

-The bound proposed by the paper uses the frameworks of Pentina et al. and Rothfuss et al. that rely on the McAllester version of a PAC-Bayes bound. However, there exist tighter version, like the Seeger one, which may help to have even tighter bound, but at a price of a higher complexity and to derive new specific studies.

-line 157 and also l166, the distribution on which expectation of m'_i is not indicated, should you define an other environment that depends on S_i and D_i.

-A point that is a bit puzzling is that since the framework can be interpreted for deriving the algorithms MAML and REPTILE, one can then learn with these algorithms while optimizing a PAC-Bayes bound. I would then expect a better behavior for these 2 approaches.
That being said, if we reinterpret these two algorithms with the proposed framework, can we explain by the bound why these algorithms would perform worse than PACMAML? Is it because of the optimization problem that is significantly harder to optimize, or is it because the considered Gibbs posterior is not well adapted for these algorithms, or maybe there is another reason?
 

-----
After rebuttal
-----
Thank you for the answers provided.

On the remark about information on the posterior, maybe considering bounds that involve information on the diversity of the voters can be interesting, such as:  
*the C-bound: Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy.
Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm. Journal
of Machine Learning Research, 16, 2015.  
*or 2nd order bounds: Andres R. Masegosa, Stephan S. Lorenzen, Christian Igel, Yevgeny
Seldin. Second Order PAC-Bayesian Bounds for the Weighted Majority Vote. 
NeurIPS 2020.

limitations_and_societal_impact: In the conclusion, the authors mention a limitation related to the fact that the method does not consider the domain shift setting.

This was not mentioned in the paper, but this work is mainly fundamental and is not subject directly to negative social impact.
review_title: null

Meta-review: All reviewers and myself agree on the interest of the topic for the NeurIPS community, on the significance of the results, and on the clarity of the contributions. The discussion phase allowed to satisfactorily address the few concerns expressed by the reviews. As pointed out by a reviewer, the submission provides valuable insights on meta-learning generalisation bounds when the base learner has access to small amounts of data, which in some cases leads to tighter bounds. This observation helps to mitigate the distributional shift in the distribution over the number of samples.
Decision: Accept (Poster)