Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides information theoretic generalization bounds for meta-learning that 1) are algorithm and data dependent 2) don't depend on the norm of the gradients, but their sensitivity to the training data. This leads to stronger bounds than previous literature. Experiments on simulated data and Omniglot with the SGLD optimization algorithm confirm the theory.
main_review: # Originality and significance #

This paper is primarily of theoretical interest to other researchers. It appears to be the second to provide information-theoretic data-dependent generalization bounds for meta-learning, after Jose and Simeone (2020). The bounds provided here appear to be tighter, as they are conditional on the meta-information $U$ for joint training and the support sets for alternate training. I cannot speak to the novelty of the mathematical tools used, as I do not work in this area.

# Quality #

Although I did not check the proofs in detail, the results appear to be sound. The experimental results validate the claim that their bounds are superior to those that rely on the norm of the gradient. However, I think in order to support other claims made in the paper, it would be helpful to 1) compare the bounds to the generalization error estimated using test data and 2) compare the bounds empirically to those of Jose and Simeone (2020).

# Clarity #

I found the paper to be well-written and clear. I would recommend that the authors move the legends of figures 2 and 3 below - the text is somewhat difficult to read.

# Update after reading response and other reviews #

I have decided to raise my score from 6 to 7, as the new empirical results addressed my concerns, with the understanding that they will be included in the final draft.
limitations_and_societal_impact: # Limitations #

The authors state that their work is limited to randomized algorithms.

# Societal impact #

I agree with the authors that there is no potential negative impact of the work, since it is primarily theoretical.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper extends recent information-theoretic approaches for computing model generalization to the meta-learning setting. They prove algorithm/data-dependent bounds for both the joint-training and support-query meta-learning strategies and instantiate the results for variants of gradient-based meta-learning with noise injection. Finally, they compute generalization bounds on synthetic and Omniglot data.
main_review: Following the author response I have increased my score under the assumption that the additional discussions of closely related work and the new empirical generalization error results appear in the revised version.

# Original review

The extension of single-task information-theoretic generalization bounds to the meta-learning setting, together with the use of gradient incoherence-based bounds, seems like a meaningful and useful theoretical contribution. I lean towards acceptance of the paper, although I do believe there is not a significant amount of practical insight provided and the some experimental results and comparisons are missing, as discussed below; I think including them would significantly improve the paper.

### Strengths:
1. The paper proves new information-theoretic meta-learning generalization bounds. The bounds are algorithm/data-dependent and, when instantiated for MAML-like algorithms, rely on gradient incoherence rather than the gradient norm, allowing them to yield non-vacuous results. 
2. Results are provided for both the joint training and support-query settings, which is an important direction for understanding meta-learning.
3. Experimental results demonstrate the usefulness of the bounds.
4. Code is released.

### Weaknesses:
1. I believe the paper would be significantly improved with more discussion comparing the results here directly to past work on meta-learning and information-theoretic generalization bounds. For the former, as discussed in the comments there are several recent papers that explicitly discuss the support-query approach and make direct comparisons to joint training. I believe there are useful comparisons to be made with the results in this paper. For the latter, while there is a comparison to single-task results, it is unclear how related the theory is. Are the proofs related or different from standard results and instantiations in this setting? I am not an expert there and so it is difficult to discern.
2. Experimentally, I believe it would be useful to compare the computed bounds with observed generalization error. This should certainly be doable for synthetic data and likely also for Omniglot. I believe this is important to give an understanding of how far away we are theoretically from practical performance.

### Comments:
17: This is not true of all few-shot learning algorithms, e.g. Reptile.  
19: Papers by Denevi et al. (2019), Bai et al. (2021), and Saunshi et al. (2021) do discuss this in-depth.  
102: The notation for a hypothesis w is lower-case on this line but upper-case in the inequality below. This inconsistency also appears elsewhere.  
167: This reinforces the result of Bai et al. (2021), who showed that joint training is not asymptotically unbiased in the agnostic setting.    
328: Doesn’t this make the meta-test distribution different from the meta-train distribution?

### References:
Bai, Chen, Zhou, Zhao, Lee, Kakade, Wang, Xiong. _How important is the train-validation split in meta-learning?_ ICML 2021.  
Denevi, Ciliberto, Stamos, Pontil. _Learning to learn around a common mean._ NeurIPS 2019.  
Saunshi, Gupta, Hu. _A representation learning perspective on the importance of train-validation splitting in meta-learning._ ICML 2021.
limitations_and_societal_impact: Adequate.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper extends information-theoretic bounds (Xu and Raginsky [15]) to provide generalization bounds for two meta-learning settings: Joint Training (classical setting of Baxter) and Alternate Training (that includes the MAML algorithm). The general bounds are based on the mutual information between the learning algorithm output and input. The bound is given a more explicit form for the case of a meta-SGLD algorithm, that can be described as a stochastic variant of the popular MAML algorithm. Experimental results show bounds that are orders of magnitudes smaller than norm-based bounds.
main_review:  Strengths:

- The results of Theorem 5.1, 5.2, and 6.2  seem very interesting, as they provide a new viewpoint to analyze the generalization properties of meta-learning algorithms.
In particular, Thm 5.2 sheds light on meta-learning settings with dataset split and shows a trade-off in choosing the split sizes.
- The Meta-SGLD algorithm and its generalization guarantees seem significant since it depends on the gradient differences rather than on the Lipschitz constant of the loss (as in previous work), which can be very large in deep learning settings. 
****************************
Weaknesses:

- The main paper is well-written and easy to follow. However, the proofs are harder to follow (especially for Thm 5.1 and 5.2).  
I suggest starting the proofs with a high-level explanation and giving motivation to each step.

- The bounds in the experiments are not compared to the actual generalization gap. The figures show a generalization gap as small as 0.1. I think it is important to validate that the actual generalization gap is smaller than that.

- The clarity of the experiment should be improved.  The figures lack axes annotations. I couldn’t see a description of what is plotted. What exactly is the G_Norm bound? How is it evaluated?

Comments:
- Thm 6.1 and 6.2 show a trade-off in choosing $T$. It would be interesting to discuss and investigate it more.

****************************

Minor comments:
- Thm 5.2: $I^{S^{tr}}$ is undefined (only defined in the appendix)



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: The authors derive two bounds on the generalization property of meta-learning algorithms using an information-theoretic analysis. The first one considers algorithms based on a *joint-training*, i.e.  when all the data from the tasks is used to update the parameters. The second bound is specific to algorithms learned through an *alternate training*, i.e. the tasks data are split into training and validation, training part is used to update the task-specific parameters and the validation part is used to update the meta-parameters.
Then, they analyze two concrete algorithms based on SGLD, a joint-training version and an alternate training version, to derive the bounds for these specific cases.
Finally, they empirically estimate the values of their bounds and compare with an empirical estimate of a previous bound based on the lipschitz constant of the network. The empirical estimation is done on synthetic data and the omniglot dataset.
main_review: __**Originality:**__  The authors specifically studied the generalization of meta-learning algorithms through the lens of information theory. They obtained bounds depending on the mutual information between the data and the outputs of the meta-learner and the base learner, similar to what was obtained in the general case of any randomized algorithm (Xu and Raginsky [15]). The authors discuss their results and compare them with other previously obtained bounds. However, I think that the authors could emphasize more the differences in their approach that allowed them to obtain different results. The only explanation of the specificity of their approach is detailed in the proof of theorem 5.1 in the supplementary material. If I understand correctly, they do not separate the environment error and the task error, which allows them to have a tighter bound. 

__**Quality:**__  The approach used by the authors seems correct, and the bounds obtained are tighter than previous results. The authors provide in the experimental section an *estimation of the values* obtained in their bounds in practice and compare them with an *estimate of the values* used in previous results. The authors have thus shown that, empirically, the values of the quantities involved in their generalization bounds are smaller than those of previous results that use the Lipschitz norm of the model. This is not an empirical validation of the theory, which would show that the bounds fit with the experiments.

__**Clarity:**__  The paper is very well written and well-structured, easy to read and follow. The results obtained are well detailed and compared w.r.t previous work. The explanations of the differences between the analysis done by the authors and previous analyses could be improved (as explained above). 

__**Significance:**__ The bounds obtained seem empirically tighter than previous bounds. It remains to be shown that they actually fit with the experiment. As mentioned by the authors, the analysis carried out here could inspire new methods, but it is not the object of the paper.

## Minor Remarks

- The meaning of the independent symbol between two sets should be explicitly defined (l.146).
- I think Fig.1 should be moved higher in the paper. It is mentioned on page 4 and doesn't appear until page 6. One must scroll down to see the figure the first time it is mentioned. 
- Some minor typos I noticed:
  - l.59 "different ~~the~~ *from* those"
  - l.81 "~~the~~ the"
  - l.94 "~~of~~ of" 
  - l.342 "*~~h~~as* compared to"
limitations_and_societal_impact: The work presented here is very theoretical. To study the possible negative impacts of this kind of work is to study the negative impacts of the whole field. On the other hand, contrary to what the authors say, meta-learning could also be used for harmful applications such as quick racial profiling of a user.
review_title: null

Meta-review: All reviewers agree that this paper is a solid work that contributes substantially to the theory of Meta-Learning. After the rebuttal, most reviewers found the response by the authors satisfactory and raised their score. As the AC of the paper, I also read the paper and found it novel and very well-written. I recommend acceptance of this work. 


Decision: Accept (Spotlight)