Venue: NeurIPS 2022 Conference

Reviews:

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 builds on PAC prediction sets by extending it to few-shot meta-learning settings, where there is assumed access to a i.i.d. sequence of tasks. In few-shot meta-learning, the goal is to adapt to a new task with only a few training examples. In order to hope to do this successfully, the learner is also exposed to a collection of similar tasks (i.e., i.i.d. from some distribution over tasks) before being presented with the test task. From a confidence point of view, providing theoretically valid, non-vacuous confidence sets for few-shot learning is difficult. The work of [1] first proposed a method of also using the task distribution to help derive meaningful conformal prediction sets, that have marginal coverage guarantees over the draw of calibration tasks and test task. This paper adopts this setting, but casts it under the framework of PAC prediction sets, which offer high probability guarantees about the expected mis-coverage over new tasks, conditional on observed calibration tasks. On a high-level, PAC sets is to CP sets as Meta-PAC sets are to Meta-CP sets, and offer a different set of (desireable) performance guarantees. The paper empirically validates the effectiveness (and theoretical properties) of their algorithm on simulated few-shot meta-learning datasets (i.e., K-shot N-way image classification and relation classification tasks), as well as a realistic heart attack prediction task (where the "tasks" are stratified by year and state).

[1] Few-shot conformal prediction with auxiliary tasks. https://arxiv.org/abs/2102.08898.
strengths_and_weaknesses: The paper is well-written (for the most part, see below) and the experiments are interesting. As the authors do well in pointing out, their PAC calibration framework offers several desireable guarantees that are not covered by the Meta-CP procedure. For example, Meta-PAC sets will be valid on average across all new tasks, rather than just on the (n + 1)th, marginalized over the draw of tasks {1, ..., n + 1}. Like standard PAC sets, this is nice, as it is often more practical to assume that the same fixed calibration set is reused for predictions across many future tasks. Therefore, even though prediction sets have been considered in a meta-learning setting before, this seems like a meaningful contribution.

Apart from a few specific comments/concerns, my main remark is on the readability of the presentation. Granted, I think the paper does an ok job considering the number of factors to consider simultaneously, but the notation is quite burdensome. It may be much easier to follow if a high-level, step-by-step description of what the authors want to accomplish and how they do it, is provided at the start of section 4---instead of jumping right into notation. For example, at a high-level, Meta-PAC sets are trying to find a single, shared threshold to use that 
1. On average over the random draw of calibration tasks that are used to choose this threshold...
2. and on average over the random choice of task that is used to evaluate this threshold...
3. and on average over predictions the model makes using this threshold on the new task...
4. The prediction set contains the correct label.

(Where we can replace "average" with high probability $1-\delta$, $1-\alpha$, $1-\epsilon$.)

I think this message is hinted at in various places in the manuscript, but it would be useful to say it plainly up front (obviously, not exactly in those words, but in simple, intuitive terms).

On to a few high-lighted strengths...

- The theoretical setting is appealing, and a reasonable and useful extension to Meta-CP (as stated above). 
- The calibration strategy seems correct and nice. At first I was concerned that computing PAC-thresholds for each of the calibration tasks was missing a factor of 1/N so that they are valid simultaneously, before applying the PAC method again on top of these values---as, with high probability, many $\hat{\tau}_{\epsilon, \alpha/2}(S_i, A_i)$ will _not_ be in $T_\epsilon(\theta_i, A_i)$ for large N. So we'd be calibrating the final threshold based on some "imposter" thresholds from a subset of tasks {1, ..., N}. However, my understanding is that since we only care about the output of a PAC method being i.i.d. (this is the r.v. O = PS-Binom(...) where O is valid w.p. 1 - alpha), not the output being valid itself, we do not actually need the PAC property to hold simulataneously over calibration tasks. Hence, the authors are able to avoid the 1/N factor in favor of two 1/2 factors (which is way more efficient). 
- Empirical results seem strong.

And a few weaknesses...

- It's kind of bothersome that a single threshold is used for _all_ downstream tasks; i.e., $\tau$ never gets updated, regardless of the size of the adaptation set A. In contrast, the Meta-CP method attempts to also estimate a data-dependent threshold (i.e., the adjusted quantile prediction). Therefore, when there is enough few-shot data, or significant variability across tasks, this could be better (in terms of being test-task conditionally). Here, the threshold never changes, regardless of whether the new task seems incredibly hard or incredibly easy.
- How tight are Clopper-Pearson based bounds when using small calibration task sizes? Assuming access to several hundred i.i.d. calibration tasks seems rather unrealistic, apart from very specific scenarios. The theory is technically solid, but a relatively straightforward combination of previous techniques (Meta-CP and PAC calibration). Thus I anticipate it to have only a relatively modest impact.
questions: - In the experiments it seems that you calibrate using tasks sampled from N choose k base calbration classes, and test on N choose k base (disjoint) test classes. Samples from the second are not i.i.d. w.r.t the second?
 - Lines 171-174 I can't understand. From what I can see, you simply want to estimate a value t s.t. $P(\hat{\tau}_{\alpha/2, \delta}(S) \leq t) \geq 1 - \delta$. I'm not sure what $g$ is, and adding the dummy label also seems confusing.
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work. It might be worth to expand on the last sentence of the conclusion: namely that people should understand that this algorithm is not a cure-all for few-shot confidence estimation, but one that relies on several strong assumptions, and only holds on average across new tasks. That said, it is better than nothing!
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 considers the notions and algorithms for generating a prediction set under the meta learning setting that satisfies PAC guarantees. Since there are multiple distributions involved in meta learning setting, the considered PAC notion for meta learning is different from existing notion designed for conventional machine learning setting, such as [3]. Furthermore, the meta learning setting is also different from covariate shift case considered in [6]. For example, adaptation data sets are available for a trained model to adapt these associated distributions without estimation of importance weights. Therefore, meta-PAC (mPAC) notion is proposed (Definition 3), which uses an augmented calibration set from N distributions, i.e., $p_{\theta_1}, …, p_{\theta_N}$ to generate $\varepsilon$-correct prediction set for a testing distribution $p_\theta$ whp $1-\delta$. Algorithm 1 is proposed to determine the parameter $\tau$ of prediction set, which uses a two-step strategy to first determine ($\varepsilon, \alpha/2$)-PAC estimator/threshold on each of N distributions, and then use these thresholds (with a label 1 attached to each threshold) to construct a new sample of size N to determine a threshold with ($\alpha/2, \delta$)-PAC. Theorem 1 shows the guarantee of this algorithm for ($\varepsilon, \alpha, \delta$)-mPAC.
strengths_and_weaknesses: Originality:
This paper generalizes PAC notation of conformal prediction from previous studies to mPAC in meta learning case, where multiple distributions are present, augmented calibration set is available. Algorithm is proposed to guarantee mPAC built on the existing algorithm designed for PAC prediction. 

Quality:
This paper is technically sound and theoretical analysis is clear.

Clarity:
This paper is easy to follow.

Significance: 
This paper provides insights to conformal prediction in meta learning setting.

questions: Algorithm 2 involves grid search for $\tau$. Could the authors elaborate a bit more on its computational cost/efficiency in analysis or experiment (e.g., the Granularity for searching)? Would there be any possible way to accelerate such grid search?
limitations: I think the authors adequately addressed the limitations and potential negative societal impact of their work
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: POST DISCUSSION:

The authors addressed most of my issues about readability and the attribution problem, so I have increased my score to a weak accept.

My final assessment is as follows:
I believe the proofs are correct, and the related work is correct.
I think the paper is the first to do a two-stage training-conditional guarantee, which has some value. Although this guarantee is a straightforward extension of existing results, perhaps somebody might be interested in it, and I do not believe it has appeared before.

I also believe it contributes by being the second paper to use training-conditional conformal for meta-learning. It is slightly different from the existing work by Adam Fisch et al. in that it also conditions on the tasks. Maybe somebody will find that useful!

_____________
This paper introduces a form of distribution-free uncertainty quantification guarantee into meta-learning and proposes an algorithm to achieve it. The guarantee is a triply-nested one, where the innermost integral is an expectation on a 0-1 loss. This expectation is nested within two other probabilities, conditioned on the calibration set and the meta learned parameters.  The algorithm boils down to two applications of binomial concentration. There are then extensive experiments on several meta learning tasks in vision, language, and medicine.
strengths_and_weaknesses: Strengths: I the technical results are clearly correct. The experiments are comprehensive.

Weaknesses:

(1) The guarantee provided in this paper is so complicated to interpret that I worry it will never be used.  It is already difficult enough to interpret a tolerance interval, and adding an extra parameter incurs such a high cognitive cost for the user that one may never know how to set these parameters.

(2) The paper is difficult to understand, as the writing is dense and exceedingly complicated. For example, take Figure 2. It includes a lot of extraneous information, the colors are missing, and certain aspects of the plot are not explained. What do the orientations of the stripes mean, for example? What does the box with “N” mean? Another part that is hard to read is 4.1.  There is just too much going on and I’m not sure anybody except for a very small community working on these PAC type guarantees will understand it.

(3) The technical result is not too interesting and the domain area is not novel.  The meta conformal prediction paper already provides a guarantee in this problem domain that works well, although it is marginal on the meta learned parameters. The fact that we can apply binomial concentration twice as opposed to once in order to condition again on those variables is basically an extension of existing results. Having said that, I think it is interesting and clever that we can chain the concentration argument twice. Nice work on the algorithm. 

(4) I believe there is a major attribution issue throughout the work. The idea of training-conditional prediction sets was first proposed by Vovk [21]. Rebranding it as PAC prediction sets and citing both works as the source of the idea is wrong. The idea comes from Vovk and his paper should get all of the credit for that.  Please remove all instances of the following attribution: “PAC prediction sets [3]”. The same is true of the so-called PS-Binom algorithm, which is essentially the same as that of Vovk in Proposition 2b of [21].  The paper [3] can be credited for applying [21] in a deep learning setting, but [21] should be cited as the sole inventor of this idea, in this and any future work. I also take some issue with the rebranding as PAC prediction sets as opposed to training-conditional validity, as they are exactly equivalent and the latter terminology came first. I will argue for rejection of the paper unless these attributions are amended.
questions: What does it mean for tasks to be “iid” in the real world, outside of synthetic setups? What are some realistic settings where we might expect the guarantee provided from the authors to actually hold?
limitations: I believe the limitations have been addressed. (I do not believe there are any serious ethical limitations of this paper in the first place, and ethics review should certainly not get in the way of the publication of this paper.)
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposed a method for estimating the prediction sets in the meta-test stage from the estimated prediction sets gathered from the meta-train adaptation and calibration phases. The whole process is carefully designed to satisfy the PAC setting in provide a theoretical guarantee for generating the meta-test prediction sets without calibration. The proposed method is tested on four different datasets across three application domains with competitive results. 
strengths_and_weaknesses: Strengths:
1. The proposed method is guaranteed by PAC bound. 

Weaknesses:
1. The paper is not presented in a good way. The notation is very confusing and misleading in general.
2. A big picture is missing. For example, we know that f is a pre-trained meta-model. But in Figure 1 this information is missing which may confuse the meta-learning people.  
questions: 1. In terms of evaluation, I think both predictions set error and prediction set size are considered as the measurements. Among the experiment settings, Meta-PS shows relatively low set error but in some cases set size is larger than others. I think the idea case is that both prediction set error and prediction set size are small. So can the author draw a clear conclusion for the comparison between Meta-CP and Meta-PS?
2. The authors select PS-Binom to estimate \tau. Do different estimators make difference in the performance? 
3. The score functions in lines 108 and 106 have different input spaces. Can the author explain why? My understanding is that f is a meta-learned off-the-shelf model. 
limitations: 1. The paper is not self-contain, the readers who are not familiar with [1] will have a hard time understanding this paper. I will highly suggest the authors to spent some paragraphs explaining some background. 
2. Only one meta-model, prototypical network, is applied as a score function to evaluate the proposed method. 
3. The notations are very confusing, especially those applied for the score function, and prediction set. 
[1] Park, Sangdon, et al. "PAC confidence sets for deep neural networks via calibrated prediction." arXiv preprint arXiv:2001.00106 (2019).
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 proposes a PAC prediction set algorithm for meta learning. The goal is to adapt the predictor to new unseen tasks with a few labeled training examples. Experiments on four datasets demonstrate the effectiveness of the proposed methods with  PAC guarantee while having smaller prediction set size.

strengths_and_weaknesses: Strengths:


* The paper is well-written.
* The proposed method is reasonable with theoretical analysis.
* Experiments on various domain and datasets are compared.


Weakness:



* For reusing the same meta prediction set parameter after adaptation, would be better if the meta predictions set parameters are also adapted?
* The current methods seem only applies on metric-based meta-learning methods, e.g., prototypical network. It would be better if the methods could be also applies on optimization-based methods, such as model-agnostic meta learning (MAML).
* For mini-ImageNet datasets, only 5-way classification problem is compared. It would be better if the authors can compare on more challenging, 10-way or 20-way classification.


questions: Please refer to weaknesss above.
limitations: Yes, the authors have addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: This paper considers the problem of uncertainty quantification in the meta learning setting, where the machine learning model needs to adapt to new classfication tasks. It solves this problem within the framework of conformal prediction to produce PAC prediction sets. This paper generalizes PAC notation of conformal prediction to mPAC in meta learning setting and develops an approach to guarantee mPAC by building on the existing algorithm designed for PAC prediction. Empirical results seem reasonably strong.

There was a lot of discussion for this paper which resulted in a much improved paper in terms of clarity and attribution to prior art. The paper is technically correct and is the second paper in the meta learning setting after Fisch et al. (https://arxiv.org/abs/2102.08898). The difference between Fisch et al. and the proposed approach is that this one applies the training-conditional idea twice in order to condition over tasks and calibration sets. In some sense, it is essentially a more complicated variant of an existing method. As some reviewers mentioned, it is not clear even from the empirical evaluation whether the proposed method performs better than the simple one.

Therefore, I consider this a *borderline paper*. I'm leaning towards accepting (if there is room in the conformal prediction related papers) for the following reason: not many conformal prediction researchers are working on large-scale ML problems and seeing this paper may inspire them to work on such problems.
confidence: Less certain
Decision: Accept