Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Pros: 
1 - The paper seems to be well written, have a good review of the references and necessaries for understanding the problem. 
2 - Some of the results found in the paper seem to be interesting. For instance, the asymptotic analysis provided in paper gives some insight on the performance of meta learning algorithms with the number shots, ratio of observation noise to the sampling noise and the number of tasks. 

Cons:
1 - It seems that most of the results of the paper are based on Loh (2017). It is expected that the author differentiate their contributions  with those of that reference more clearly. 
2 - Some of the notations are misleading. This is a minor issue and up to the authors to change it or not but it may help with the readability of the paper. Some notations like $\theta$ are usually used for parameters in models. In this paper, $\theta$ is used as a function. I understand why the authors decided to use it as a function but it may be a bit misleading. 
3 - Some of the assumptions in the paper can be very restrictive. For instance, it is assumed that the distributions are $2\delta$-separated while close in the KL divergence sense. Isn't this too restrictive? Maybe it is good for the authors to try to talk more about the implications of such assumptions. How does this restrict the space of interested probability distributions? 
4 - Another example of a restrictive assumption is bounded minimum singular values. How does such a restriction affect the space of considered solutions? 
5 - There has been no effort in comparing with any bounds that are available currently. 
review_title: Well written paper with potentially interesting insights on the theory of meta learning but some issues exist

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors study the performance of a meta-learner theoretically in two settings. In the first one the overall number of possible tasks is limited and tasks are close in KL-divergence. The second setting is MAP estimation for a family of linear regression tasks. Lower and upper bounds are provided on minimax parameter estimation error.

The bounds solidify common sense knowledge about the role of the number of training tasks, number of samples, and task relatedness and diversity on the performance of meta-learner and are supported by numerical examples. I am in favor of accepting this paper. I'll provide suggestions for improving presentation.

1. The assumption in the first setting is that the tasks are close in distribution space but far away in parameter space. Could you mention some examples of such set of tasks? It does not seem like a weak assumption to me, as mentioned in the paper, but then this is the nature of lower bounds. The point is not to model a typical scenario but to design hard cases that lead to high error. But in any way an example is necessary to show that this situation is possible.

2. It seems to me that the lower bound in the first setting has less to do with the performance of the meta-learner than suitability of parameter estimation error as a measure of performance. At the end of the day, it is accurate predictions, and not accurate parameters, that matter. The setting is designed so that tasks have similar distributions but quite different optimal parameters, which results in a high parameter estimation error for the meta-learner. It could be that the meta-learner in fact makes quite accurate predictions (since the tasks are actually close in distribution space) despite its high parameter error.

3. The first setting is worded generally (novel task generalization) while the second setting is presented as a more specific scenario (hierarchical Bayesian linear regression). The first time I was reading the paper I assumed that the first part describes general results on meta-learning and the second part shows a particular instance of the previous section, which was confusing as the second setting does not satisfy the assumptions in the first setting. I suggest presenting these two sections as two particular and different settings as they are.

Minor comments:

1. The statement of Theorem 1 has undefined notation. I assume I(.;.) is mutual information but it is not defined. The text defines W|\pi and Z|\pi but the equation uses \pi_{M+1} and W and Z separately. What do \pi_{M+1}, W, and Z (without the vertical bar) mean?

2. The paragraph above Corollary 1 is hard to understand. Do "training task" and "meta-training task" have the same meaning? Also, if the number of previous tasks is M \leq J-1, how can there be J previous tasks that are close?

3. What is B_2(1) in 5.1?
review_title: Good results; Suggestions for improving presentation

final_score: rating: 7: Good paper, accept
review_content: The paper studies the information-theoretic lower bounds in the minimax setting of meta-learning. The paper also discusses upper and lower bounds in the hierarchical Bayesian framework of meta linear regression. The novelty of the paper is two-fold: a) it proves a novel meta-learning local packing result to compute the conditional information between training task samples and the novel task data distribution and b) it compares the lower bound of the risk to the risk of posterior estimate in meta linear regression. In addition, the authors verify the dependence of risk on various parameters in 2 different experiments.

My major concern is that in theorem 3, $Mn$ needs to grow exponentially with $d$ to be significantly better than the case when there are no training tasks available (theorem 2). However, theorem 4 states that $Mn$ just needs to depend polynomially on the dimension $d$. Hence, the upper bound and the lower bound on the risk have a gap on the parameter $d$. Thus, it is not clear if the lower bound in Theorem 1 is tight. It would be great to have a discussion on this and the assumptions that one needs to take to improve upon this gap. 

Few other concerns:
1. In the hierarchical regression setting, the assumptions for theorem 3 and theorem 4 are different. A discussion on how the lower bounds will change, if we assume different variance of task parameters $\sigma_{\theta_1}, \cdots, \sigma_{\theta_{M+1}}$ and task-specific observed samples $\sigma_1, \cdots, \sigma_{M+1}$, will be helpful.
2.  The proof of theorem 3 focuses on packing the parameter space $\theta$ by an $\epsilon$-net on $B_2(4\delta)$, where $\delta$ is fixed later on. However, the model assumes $\theta$ coming from ball $B_2(1)$. There seems to be some mismatch in the theorem statement and the proof.   
3. The risk in theorem 4 involves few more parameters whose effect on the risk hasn't been checked in experiments e.g. the ratio of variance in observed samples of novel task v/s variance in task parameters. Also, it will be interesting to see how the results change when the data distribution is changed since the risk depends on the singular values of the data matrix. 

I have read the proofs. They are easy to read and understand. My scores are slightly on the lower side because I am concerned about the tightness of the lower bound in Theorem 1. I am happy to discuss this with the authors and other reviewers during the discussion period.

**After Rebuttal**
I have read the reviews of other reviewers and the responses of the authors to the questions posed by the reviewers and Ahmad Beirami. I understand that the authors have taken a pessimistic approach to compute the lower bounds of risk in the minimax setup of meta-learning. However, I believe the paper is an important step in this direction. Theorem 3 and Theorem 4 are important additions to the paper, which show a margin between the pessimistic lower bound of the risk and the actual risk with the introduction of structure to the learning setup. Overall,  I enjoyed reading the paper, and I have increased my score after the rebuttal.
review_title: Official Review #1

final_score: rating: 7: Good paper, accept
review_content: This paper provides a minimax novel-task risk lower bound for meta learning via information-theoretical techniques, showing the fundamental limits of meta learning. The novel-task minimax risk depends on the number of samples from the meta-training set and novel task, as well as the task similarity. The authors further investigate the meta learning problem on a hierarchical Bayesian model, discuss the lower bound and upper bound with maximum-a-posterior estimator.

Overall I feel this paper study an important problem of the meta-learning and the derivation all looks correct. The main drawback is that the presented minimax lower bound is quite pessimistic that may not fully exploit the potential task similarity in practice, but I feel it is still acceptable to first study the minimax lower bound, and leave the case with more structure as future work.

I would like to ask if there is a gap between the description at the beginning of Section 5 and the analysis starting from Section 5.1, as the bayesian model described at the beginning of Section 5 does not assume theta have ell_2 norm smaller or equal than 1, and in fact, cannot be universally hold as theta is sampled from a d dimensional Gaussian (can have high probability arguments instead). However, the analysis throughout Section 5 all have this constraint. I don’t see strong dependency on the norm of theta (e.g. in the covering number, KL bound etc) but I hope the authors check and clarify it in the next version.

One small tip: lower bound is better represented via big-Omega notation.
review_title: A good paper that investigate the fundamental limits of meta-learning in the sense of minimax novel-task risk

Meta-review: The authors study the theoretical performance of a meta-learning in two settings. In the first one the overall number of possible tasks is limited and tasks are close in KL-divergence. The second setting is MAP estimation (in a hierarchical Bayesian framework) for a family of linear regression tasks. Lower and upper bounds are provided on minimax parameter estimation error.
This paper has spurred a lot of discussion among reviewers and (competent) external commentators. Most of these criticisms were right on target, but the authors managed to convince the reviewers and myself that there was simply an issue of presentation of the main results. I suggest the authors to take into serious considerations all the aspects raised by the reviewers that has generated misinterpretations of the presented results.
Decision: Accept (Poster)