Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proves new information-theoretic generalization bounds for meta-learning, using evaluated conditional mutual information (e-CMI) which was introduced by Steinke and Zakynthinou (2020) who applied it in the context of standard supervised learning. 

In Section 3. The paper gives distribution- and algorithm-dependent generalization bounds based on e-CMI. Then, they show that they can use these results to recover existing bounds in the literature using CMI. Additionally, they prove a generalization bounds based on binary KL divergence. This allows them to prove “fast rate” bounds in the optimistic setting, when interpolation is possible. They also prove high-probability bounds for these three results. 

In Section 4. The authors instantiate these results and show that in a representation learning type of setup, their results recover existing upper bounds based on the complexity of the class used for representations and the class used for learning task-specific predictors, but the results in this paper also seem to be more general in the sense that they don’t require any assumptions.  


strengths_and_weaknesses: The paper addresses an important problem of obtaining generalization guarantees for meta-learning. I think the results provided in this paper are nice and interesting, and in particular I liked how the generic results in Section 3 can be used to recover existing results in Section 4. 

The paper is well written and easy to follow. 

questions: It might be good to clarify the learner and meta-learner that are used to establish Corollary 4, 5, and 6. 

What’s the term: N choose 2, that appears in Corollary 4,5, and 6? It’s not clear to me what this is just from reading the corollary statements.

limitations: It might be good to reflect on the results of the paper and discuss their implications with respect to the current practice of meta-learning.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper concerns the problem of understanding the generalization of the meta learning algorithms. In particular, the authors study a “two-stage” algorithm in which in the first step the meta learner learns a meta hypothesis. Then, in the second stage, based on a limited number of samples, the base learner finds the output for a particular task. 

This paper extends in a very interesting way the idea of conditional mutual information (CM) from  Steinke-Zakynthinou to the meta learning setup. In particular, they consider meta-supersample instead of only supersample as in the CMI paper. Then, they prove generalization bounds based on conditional mutual information in the same spirit as in the CMI paper. Also, they provide a high probability bound in Section 4.


strengths_and_weaknesses: 
I think the most interesting aspect of the paper is providing an algorithm-dependent and distribution-dependent generalization bound for the meta learning problem. Also, the bounds are not loose as shown in Section 4. 
 
Regarding weakness, the presentation of the additional structure to define the supersample structure should be improved. 
Also, one of my concerns is that prior work on meta learning studies the “excess-risk”. However, in this work the authors study the generalization error. There is no discussion in the paper on why studying the generalization error instead of excess risk is interesting. 
The next major weakness is that this work does not introduce any “task-relatedness” notion. 

Also, the authors should spend more time on discussing the difference between their work and very related work of [35].

questions: - One major question is why is the generalization gap important in meta learning? Note that the results of Tripuraneni et al concern the “excess risk” of the two-stage algorithm.

- The results in the paper do not give us any notion of task relatedness. It is opposed to the results in the transfer learning and meta learning literature in which we are mainly interested in answering when it is possible to do transfer learning.

- Can your results tell us when meta learning is not possible? Or when is the performance of the two-stage algorithm not good?

- The setup in the paper by Tripuraneni et al  is quite different from the general setup in the paper.

- Corollary 4 does not represent the power of the bounds. The bounds are worst-case bounds. As stated in the intro, we are interested in the algorithmic- and distribution- dependent results.

- The construction of the supersample was previously proposed in [35]. However, the bounds in this paper have better dependence on the number of samples. I think the authors should clarify the main technical differences between their proof idea and the proof idea in [35].

- What is the application of the bound to more practical algorithms such as MAML?


limitations: The authors did not discuss the limitations of their work in the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper provides information-theoretic bounds for meta-learning with the recent e-CMI framework. At first, two square-root average e-CMI bounds are obtained with the two-step and one-step proof techniques, which are tighter than the previous corresponding information-theoretic bounds. Then the bounds are improved to faster rate decay ($\frac{1}{n\hat{n}}$) w.r.t the number of samples and number of tasks with the binary KL divergence. Next, the one-step and two-step e-CMI bounds are further extended to the high-probability setting. Finally, assuming the finite Natarajan dimension for the representation function set and finite VC dimension for the prediction function set, the expressiveness of e-CMI bounds is demonstrated to recover the scaling behaviors of meta-learning bounds obtained with classical learning theory. 
strengths_and_weaknesses: ### Strengths
1. The paper presents theoretical results that bridge the information-theoretic meta-learning and the classical meta-learning theories. 

2. The author first proposes the meta-learning bounds with the e-CMI framework, which are tighter than previous mutual information bounds.

3. The whole work is solid and the proof is clear. 

### Weaknesses
1. The proof techniques are adapted from previous works, the one- and two-step bounds are based on previous proof ideas and the binary KL divergence bound is common in PAC Bayes theory. 

2. The notations are a little cumbersome. Section 2 and the description for Figure 1 are redundant and hard to follow. 

3. Lack of empirical validations. 
questions: ### suggestions
I suggest the author present Section 2 in a more logical way and simplify the notations if possible. For example, firstly introduce the original e-CMI framework that adopts supersample. Then to adapt the original e-CMI framework to meta-learning, the paper proposes the meta-supersample, which contains both ghost tasks and ghost task-specific samples, then introduce the membership, etc... 

### Minor issues

1. Line 119 $\mathcal{R}^{\hat{n}}$
2. $\mathcal{F}$ undefined in 155
3. Appendix equation 28 and 29, $\gamma^2$ should be $\frac{\gamma^2}{2}$
limitations: The similarity and difference to previous Gaussian complexity bounds are mentioned when discussing the expressiveness for recovering the scaling behavior of classical learning theory.
review_title: null

Meta-review: metareview: The reviewers agree that this is a solid contribution. Please do revise the paper according to the reviewers comments and the discussion.
confidence: Certain
Decision: Accept