PAC Prediction Sets for Meta-Learning
Authors: Sangdon Park
Edgar Dobriban
Insup Lee
Osbert Bastani
Venue: NeurIPS 2022 Accept (2022)
Keywords: uncertainty quantification
prediction sets
probably approximately correct
conformal prediction
meta learning
few-shot learning

Abstract: Uncertainty quantification is a key component of machine learning models targeted at safety-critical systems such as in healthcare or autonomous vehicles. We study this problem in the context of meta learning, where the goal is to quickly adapt a predictor to new tasks. In particular, we propose a novel algorithm to construct \emph{PAC prediction sets}, which capture uncertainty via sets of labels, that can be adapted to new tasks with only a few training examples. These prediction sets satisfy an extension of the typical PAC guarantee to the meta learning setting; in particular, the PAC guarantee holds with high probability over future tasks. We demonstrate the efficacy of our approach on four datasets across three application domains: mini-ImageNet and CIFAR10-C in the visual domain, FewRel in the language domain, and the CDC Heart Dataset in the medical domain. In particular, our prediction sets satisfy the PAC guarantee while having smaller size compared to other baselines that also satisfy this guarantee.

PAC Prediction Sets for Meta-Learning
Sangdon Park
Edgar Dobriban
School of Cybersecurity and Privacy
Dept. of Statistics Data Science
Georgia Institute of Technology sangdon@gatech.c edu
The Wharton School
University of Pennsylvania
dobriban@wharteo upenn edu
Insup Lee
Osbert Bastani Dept. of Computer Info. Science PRECISE Center
Dept. of Computer Info. Science PRECISE Center University of Pennsylvania lee@cis upenn. edu
University of Pennsylvania obastani @seas upenn edu
Abstract
Uncertainty quantification is key component of machine learning models targeted at safety-critical systems such as in healthcare or autonomous vehicles. We study this problem in the context of meta learning, where the goal is quickly adapt a predictor to new tasks. In particular, we propose a novel algorithm to construct PAC prediction sets, which capture uncertainty via sets of labels, that can be adapted to new tasks with only a few training examples. These prediction sets satisfy an extension of the typical PAC guarantee to the meta learning setting; in particular, the PAC guarantee holds with high probability over future tasks. We demonstrate the efficacy of our approach on four datasets across three application domains: and CIFAR 10-C in the visual domain, FewRel in the language domain, and the CDC Heart Dataset in the medical domain. particular, our prediction sets satisfy the PAC guarantee while having smaller size compared other baselines that also satisfy this guarantee.
Introduction
Uncertainty quantification is a key component for safety-critich systems such as healthcare and robotics, since enables agents account for risk when making decisions. Prediction are promising approach, since they provide theoretical guarantees when the training and test data are and online learning [
i.i.d. 0 4 there have been extensions to handle covariate shift 5 6
We consider the meta learning setting, where the goal is to adapt an existing predictor to new tasks using just a few training examples [ 10) 12 [3]. Most approaches follow steps: meta learning (i.e., learn a predictor for fast adaptation) and adaptation (i.e., adapt this predictor to the new task). While there has been work on prediction sets in this setting (4), key shortcoming that their guarantees do not address some important needs in meta learning; in particular, they do not hold with high probability over future tasks. For instance, autonomous driving, the future tasks might be new regions, and correctness guarantees ought to hold for each region; in healthcare, future tasks might be new patient cohort, and correctness guarantees ought to hold for each cohort.
We propose an algorithm for constructing probably approximately correct (PAC) prediction sets for the meta learning setting. As example, consider learning image classifier for self-driving cars as our use case (Figure Dp. Labeled images for image classifier learning are collected, with different regions representing different but related tasks (e.g., New York, Pennsylvania, and California). The
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

meta learning and calibration
task dataset
task dataset
adaptation set A
calibration set
adaptation set A
calibration set
person
person
FA
F
adaplation
inference
task dataset plo
task dataset ps
adaptation set A
evaluation set
M
Pfy $A
car
person
car
person
car
person
Figure I: Learning for PAC prediction sets with fast adaptation. In meta learning and calibration, the PAC prediction set parameter is chosen from multiple task datasets given meta-learned and adapted score function f using any meta-learning algorithm and an adapted PAC prediction set FA. (e.g., an image classifier and prediction set are learned over labeled images from various regions, including New York). In adaptation, the score function is adapted to the new task distribution f (e.g.. the image classifier is adapted using labeled images from Alaska). In inference, by using the same parameter t used without additional calibration, the constructed and adapted prediction set FA has correctness guarantee for most of future examples (e.g., the prediction set along with the adapted image classifter has a correctness guarantee over most images from Alaska). Importantly, the correctness guarantee (error below is achieved with probability at least (1) 1 - å over the calibration sets in the meta learning phase and (2) - & over an adaptation set in the adaptation phase. This explains why we use three-parameter PAC-style guarantee for meta learning.
goal is to deploy this learned image classifier way, egg., minimizing label gathering cost on labeled images from Alaska for the classifier adaptation.
target region (e.g., Alaska) in a cost-efficient
Due to the safety-critical nature of the task, it is desirable to quantify uncertainty in a way that provides rigorous guarantees, where the guarantees are adapted to a new task (e.g., Alaska images) i.e. they hold with high probability specifically for future observations from this new task. In contrast, existing approaches only provide guarantees on average across future tasks [4]
Our proposed PAC prediction set starts with meta-learned and potentially adaptable score function as our base predictor (using standard meta learning or few shot classification approach). Then, we learn the parameter of prediction set for meta "calibration" by using calibration task distributions (e.g., labeled images from Texas and Massachusetts). Given a test task distribution (e.g., labeled images from Alaska), we only have few labeled examples for adapting the score function to this target task without further updating the prediction set parameter, which potentially saves additional labeled examples. We prove that the proposed algorithm satisfies the PAC guarantee tailored to the meta learning setup. Additionally, we demonstrate the validity the proposed algorithm over four datasets across three application domains: mini-ImageNet [T0] and CIFAR 10-C 155 in the visual domain, FewRel 16 in the language domain, and CDC Heart Dataset 17 in the medical domain.
2
Related Work
Meta learning for few-shot learning. Meta-learning follows the paradigm of learning-to-lee - usually formulated as few-shot learning: learning adapting model to new task distribution

---

Existing approaches propose neural network for few-shot learning. However, there is no guarantee that these approaches can quantify uncertainty properly, and thus they do not provide guarantees for probabilistic decision-making.
by leveraging a few examples from the distribution. predictors or adaptation algorithms [T III
12 [3
The classical goal in conformal prediction (and inductive conformal pre- diction) I [9] is find prediction set that contains the label with a given probability, with respect to randomness in both calibration examples and a test example, where a score function (or non-confornity score) is given for the inductive conformal prediction. This property is known as marginal coverage. If the labeled examples are independent and identically distributed (or more precisely exchangeable), prediction sets constructed via inductive conformal prediction have marginal coverage [19 2 However, the identical distribution assumption can fail if the covariates of a test datapoint are differently distributed from the training covariates, i.e., covariate shift occurs. Assuming that the likelihood ratio is known, the weighted split conformal prediction set [5] satisfies marginal coverage under covariate shift. So far, we have considered only two distributions, calibration distribution and test distribution. In meta learning, a few examples from multiple distributions are given, providing a different setup. Assuming exchangeability of these distributions, conformal prediction sets for meta learning have been constructed, covering over a random sample from new randomly drawn distribution, exchangeable with the training distributions [4] In statistics, two-layer hierarchical models consider examples drawn from multiple distributions. while assuming examples and distributions are independent and identically distributed; these are identical to the model of meta-learning we study. Several approaches to construct prediction sets (e.g., double conformal prediction) satisfy the marginal coverage guarantee (20
Conformal prediction.
PAC prediction sets. Marginal coverage is unconditional over calibration data, and does not hold conditionally over calibration data (i.e., with specified probability for fixed calibration set). Training conditional conformal prediction was introduced as way to construct prediction sets with PAC guarantees 21: Specifically, for independent and identically distributed calibration examples, they construct a prediction set that contains a true label with high probability with respect to calibration examples; thus, these prediction sets cover the labels for most future test examples. This approach applies classical techniques for constructing tolerance regions 22 to the non-conformity score to obtain these guarantees. Recent work casts this technique in the language of learning theory [.) informing our extension to the meta-learning setting: thus, we adopt this formalism in our exposition. PAC prediction sets can be constructed in other learning settings -.g., under covariate shift (assuming the distributions are sufficiently smooth (6 or well estimated (7). In the meta learning setting, the
meta conformal prediction set approach also has a PAC property [4] but does not control error over the randomness in the adaptation test examples. In contrast, we propose prediction set satisfying
a mela-PAC property-i.e. separately conditional with respect to the calibration data and the test
adaptation examples; see Section 4.1 for details.
3 Background
3.1 PAC Prediction Sets
We describe ceining-conditionss inductive conformal prediction strategy for constructing probably approximately correct (PAC) prediction sets (21), using the reformulation as a learning theory problem in 3 Let X' be a set of examples or features and y be a set of labels. We consider a given score function X x y + Rzo, which is higher if ) is the true label for E X. We consider parametrized prediction set; letting 7 E R2o. we define prediction set F, X + 2 as follows:
Fx(x) = V 1 (z. v) 2 r).
Consider a family of distributions (po)oge over 2 = X' x V, parametrized by 0 E θ. For an
unknown 0 we observe independent and identically distributed (i.id.) calibration datapoints S ~ Pp- We define a prediction set, or equivalently the corresponding parameter т, to be e-correct, as follows:
Definition 1. A parameter 7 E R2o is e-correct for ps if
P(Y E F+(X) 11002-1-0 1-
(1)
where the probability is taken over (X, Y) Pa.
3

---

Letting T. (0) be the set of satisfying ① for pg. we can write E (0) S R20 if T is e-correct for Po- If an estimator of is E-correct on most random calibration sets Pg. we say is PAC.
Definition 2. An estimator i + Rzo is ( proobaby approximately correct (PAC) for pe if
IP (SE, E (T())) 2 d,
where the probability is taken over S.
Along with the PAC guarantee, the prediction set should be small in size. Here, by increasing the scalar parameterization, we see that the expected prediction set size is decreasing with an increasing prediction set error (i.e., Px, (Y & Fr (X))). Thus, a practical (e, 6)-PAC algorithm that implements the estimator %e,ō maximizes T while satisfying a PAC constraint to minimize the expected prediction set size
3.2
Meta Learning
Meta learning aims to learn a score function that can be conveniently adapted to a new distribu- tion, also called a lask. Consider lask distribution Pn over θ, and M training task distributions Pe,....,PP. where .I..... MM is an i.i.d. sample from Px- Here, we mainly consider meta learning with adaptation (e.g., few-shot learning) to learn the score function, while having learning without adaptation (e.g., zero-shot learning) as a special case of our main setup.
For meta learning without adaptation, labeled examples are drawn from each training task distribution to learn the score function / : X' x y + Rzo. and the same score function is used for inference (i.e., at test time). For meta learning with adaptation. adaptation examples are also drawn from each training task distribution to learn the score function f Z' x X' x y - R20, and the same number of adaptation examples are drawn from new test task distribution for adaptation. Given an adaptation set A E Zt, the adapted score function is denoted by fA X' x y + Rgo, where A v) == (AA x, y). We consider Y large enough to include all label classes, some of which possibly seen during testing but not during training. This formulation includes learning setups (e.g., few-shot learning) where unseen label classes are observed during inference, by considering different distributions over labeled examples during training and inference.
4 Meta PAC Prediction Sets
We propose a PAC prediction set for meta learning. In particular, we consider a meta-learned score function, which is typically trained to be a good predictor after adaptation to the test distribution. Our prediction set has correctness guarantee for future test distributions.
There are three sources of randomness: (1) an adaptation set and calibration set for each calibration task, (2) an adaptation set for a new task, and (3) an evaluation set for the same new task. We control the three sources of randomness and error by ö, a, and E, respectively, aiming to construct a prediction set that contains labels from new task. Given meta-learned model, the proposed algorithm consists of two steps: constructing prediction set captured by a specific parameter to be specified below for each calibration task (related to and a). and then constructing prediction interval over parameters (related to and 8).
Suppose we have prediction sets for each task, parametrized by some threshold parameters. Suppose that, for each task, the parameters only depend on an adaptation set for the respective task. As tasks i...d, the parameters also turn out be i.i.d.. The distribution of parameters represents possible range of the parameter for a new task. In particular, if for each task, the prediction set contains the true label a fraction achieve e-correct prediction sets for new task. Based on this observation, we construct a prediction interval that contains a fraction 1 of e-correct prediction set parameters. However, the parameters of prediction sets need to be estimated from calibration tasks, and the estimated parameters depend on the randomness of calibration tasks. Thus, we construct prediction interval over parameters which accounts for this randomness. The interval is chosen to be correct (i.e., to contains e-correct prediction set parameters for fraction a of new tasks) with probability at least over the randomness of calibration tasks.
of the time, the distribution of the parameters suggests how one may

---

1(Y f S))
F-(X))
(a) Marginal guarantee
(b) PAC guarantee
21
N
N
1(2 FAA.:
1(Y $ F+(A.x))
(c) Meta task maskinarginal guarantee
IE!
(d) Meta PAC guarantee (ours)
Figure 2: Comparison among different guarantees prediction sets. An edge A + B between random variables A, B represents that B is drawn conditionally on A, and plate with the symbol N represents that there are N copies the variables it, indexed by .......V. Each stripe pattern with different color indicates that the corresponding random variables are simultancously conditioned on in the correctness guarantee; 1" denotes conformal prediction set. Thus, for instance, in (d), there is a 1 probability of correctness with respect to the test datapoint (x, v). a a probability of correctness with respect to the test task and its adaptation data (0, A), and 1 - probability of correctness with respect to the calibration tasks, their calibration data, and their adaptation data (O., S,, A:) for i = I,..., ......,N N. The proposed meta PAC prediction set (2d) has most fine-grained control over the correctness guarantee conditioning over calibration tasks, the test task and adaptation set, and the test data.
4.1 Setup and Problem
We describe the problem on PAC prediction set construction for meta learning with adaptation; see Appendix A for simpler problem setup without adaptation, special case of our main problem.
Setup. the setting of Section 3.2 the training samples from some training distributions poz- .... M are used to learn score function via an arbitrary meta learning method, including metric-based meta-learning [1]] and optimization baased meta-learning [[2]. We denote the given meta-learned score function by f. Additionally, we have N calibration distributions .a.,.... Pa where .,..., ON is an i.i.d. sample from Pa. i.e., : (0......40 ON) ~ p From each calibration distribution ps,, we draw n i.i.d. labeled examples for calibration set, i.e., S == (S),... Sx) PØ, ... ,. and S E = gaxN Additionally, we draw i.i.d. labeled examples for an adaptation set, i.e., A = (AI.... AN) ~ Ph. ... ..Pb, and A E A == z we use them to construct the meta PAC prediction set. Finally, consider labeled adaptation examples A, i.e., A pt., and i.i.d. evaluation examples.
i == I.....
distribution pa. where 0 ~ Pr. From it, draw i.i.d.
Problem. Our goal is to find prediction set F, Z' X - 2 parametrized by E R20 which satisfies a meta-learning variant the PAC definition. In particular, consider an estimator f: S A T2zo that estimates for prediction set, given augmented calibration (S, A). Let (0, A) be a set all e-correct parameters 7 with respect to adapted using a test adaptation set A. We also consider F.A (x. y) (,, x. y)-
We say that a prediction set Fr parametrized by T is e-correct for pe for a fixed adaptation set A, E T. (0, A). Moreover, want the prediction set F, where is estimated via i to be correct most test sets for adaptation and for most test tasks 6, i.e., given S E S and A E A.
Pf5 A) ET A)} 2
5

---

where the probability is taken over and A. Intuitively, we want a prediction set, adapted via A, to be correct on future labeled examples from Po- Finally, we want the above to hold for most augmented calibration sets (S, A) from most calibration tasks .1,....0y, ON. leading to the following definition.
Definition 3. An estimator i (mPAC) for pm
S x A Rz0 is (E, 6m-meta probably approximately correct
P (P(+(S.A)
21 21-a321-6,
where the outer probability is taken over 0, S and A. and the inner probability is taken over A and A.
Notably, Definition 5 is tightly related to the PAC definition of meta conformal prediction 14 We illustrate the difference Figure 2 the figure represents the different guarantees of prediction sets via graphical models. Each stripe pattern indicates the random variables that are conditioned on in
the respective guarantee. Figure 2 represents the proposed guarantee, having Figure 2b and 7b as
special cases. Figure 2c shows the guarantee of meta conformal prediction proposed in 14 also having Figure 2a and 7a as special cases, Figure [ shows that the proposed correctness guarantee conditioned over calibration tasks, adaptation set A from test task, and test data (æz, y). This implies that the correctness guarantee of an adapted prediction set (thus conditioned on the adaptation set) holds on most future test datasets from the same test task. In contrast, the guarantee in Figure 2 conditioned on the entire test task. Thus, the correctness guarantee does not hold conditionally over adaptation sets; this means that the adapted prediction set (thus conditioned set) does not need to be correct over most future datasets the same task.
adaptation
4.2 Algorithm
Algorithm 1 Meta-PS: PAC prediction set for meta-learning. Internally, any PAC prediction set algorithms are used to implement an estimator Re,8; we use PS-BINOM (Algorithm) 2 in Appendix B
I: procedure META SSIN, A. g.g.e. ........ N) do PS APS-BINOM(SI, f ,,,
for (1....;N)
3:
(D) Use Algorithm
2 Appendix
4: S' - ()......... (TN,
T --PSSBINOM(S 0,
6:
return 5
Next, we propose our meta PAC prediction set algorithm for an estimator i that satisfies Definition while aiming to minimize the prediction size, by leveraging the scalar parameterization of prediction set. The algorithm consists of two steps: find prediction set parameter over labeled examples S, and A, from the i-th calibration task distribution, and find a prediction set over the parameter of prediction sets in the previous step. At inference, the constructed prediction set is adapted to a test task distribution (i.e., implementating an (e, -PAC estimator 7c,5), we can use any PAC prediction set algorithms (e.g., Algorithm P in Appendix B).
an adaptation set A. Importantly, in finding prediction sets
Meta calibration. For the first step. for each i E {1,..., N}. we estimate prediction set parameter (5::) satisfying a (e, a/2)-PAC property using a calibration set S; and score function adapted via an adaptation set A,, leading to fA. by using any meta learning and adaptation algorithm. We consider the N learned prediction set parameters-wwitt the convention of the PAC prediction set algorithm- to form new labeled sample, i.e., S' 1)).
dummy label 1 to fit
((fc,a/2(Si), (f... (fe,,a22(NN).
In the second part, we construct an (a/2, PAC prediction set for the threshold 7 using S' and score function g defined as g(T, y) 71 = 1), where 1(.) is the indicator function A Thus, the constructed prediction set can be equivalently viewed as an interval (l.22.(55)) oc) where the
thresholds of most calibration distributions included; Section 4.3 for formal statement along with intuition on our design choice, and see Algorithm for an implementation.
is also called training-soe set conditional guarantee 21
'The constructed prediction set parameter is equivalent to satisfying Ps [r S fe.a/a(S)) 2 1 - a/2 with probability at least over the randomness of Si..... ... Sy used estimate

---

Adaptation and inference. We then use labeled examples A from a test distribution to adapt the meta-learned score function as in the meta calibration part. Then, we use the same parameter *(S, A) of the meta prediction set along with the adapted score function as our final meta prediction set (A(S.A) for inference in the future.
Reusing the same meta prediction set parameter after adaptation is valid, as the meta prediction set parameter also chosen after adaptation via hold-out adaptation set from the same distribution as each respective calibration set. Moreover, by reusing the same parameter, we only need a few labeled examples from the test distribution for an adaptation set, without requiring additional labeled examples for calibration on the test distribution. Finally, we rely on a PAC prediction set algorithm that aims minimize the expected prediction set size 2 3]; Algorithm relies on this property, thus making the meta prediction set size small.
4.3 Theory
The proposed Algorithm I outputs a threshold for a prediction set that satisfies the mPAC guarantee, as stated in the following result (see Appendix C for proof);
Theorem 1. The estimator i implemented in Algorithm 7 is at ( 8) Pr.
Intuitively, the algorithm implicitly constructs an interval /2./2. 20) over scalar parameters of prediction sets. In particular, for the i-th distribution, the Algorithm in Line 3 finds scalar parameter of a prediction set for the i-th distribution, which forms an empirical distribution over the scalar parameters. Due to the i.i.d. nature of 0, i = I,..., NN, the parameter of prediction set for test distribution follows the same distribution over scalar parameters. Thus, choosing a conservative scalar parameter as in Line 5 of the Algorithm suffices to satisfy the mPAC guarantee.
5 Experiments
We demonstrate the efficacy of the proposed meta PAC prediction set based on four few-shot learning datasets across three application domains: domain, FewRel [16] for the language domain, and CDC Heart Dataset [ for the medical domain. See Appendix for additional experiments, including the results for CIFARIO-C.
[10) and CIFAR10-4 [[5] for the visual
5.1 Experimental Setup
Few-shot learning setup. We consider k-shot c-way learning except for the CDC Heart Dataset; In particular, there are classes for each task dataset, and k adaptation examples for each class. Thus, we have ( = ke labeled examples to adapt model to a new task. As the CDC Heart dataset is label unbalanced dataset, do not assume equal shots per class.
Score functions. We use a prototypical network [ a score function. uses t adaptation examples to adapt the network to given task dataset, and predicts labels on query examples.
Baselines. We compare four approaches, including our proposed approach.
PS: We consider a naive application of PAC prediction sets 3 We pool all nN labeled examples from calibration datasets into one calibration set to run the PAC prediction set algorithm.
PS-Test: We construct PAC prediction sets by using 20 shots for each class directly drawn from the test distribution.
Meta-CP: We use the PAC variant of meta conformal prediction [1], which trains a quantile predictor along with a score function, while our approach only needs a score function. We run the authors' code with the same evaluation parameters for comparison.
Meta-PS: This is the proposed meta PAC prediction set from Algorithm
Metric. We evaluate prediction sets mainly via their empirical prediction set error over test sample, i.e., having learned a parameter T, we find |/| (x.))e 1y & FF(x))) where A is an adaptation set, and E is an evaluation set drawn from each test task distribution. We desire this to be at most given fixed calibration and test datasets. This should hold with probability at least randomness due to the calibration and adaptation data; and with probability at least 1 - a over the randomness due to the test adaptation set. To evaluate this, we conduct 100 random trials, drawing independent calibration datasets, and for each fixed calibration dataset, conduct 50 random trials
d over the
7

---

0.35
8
0.10
prediction set size
0.30
0.25
prediction
0.20
0.15
0.10
0.05
0.00
PS-lest
Meta-CP
(a) Error
(b) Size
0.200
Meta-CP
prediction set error
0.175
Meta-PS
0.125
0.100
0.050
0.025
calibration distribution index
Error given an augmented calibration set
Figure 3: Prediction set
Ba
size
3ap. and error given calibration set 3eh mini mini-ImageNet.
Parameters are = 500, n 2500, 25, e = 0.1, a 0.1, = 10 for Meta-PS and & = 0.1, 5 10-5 for the other methods.
drawing independent test datasets. The prediction set size evaluation is done similarly the error; we compute the empirical prediction set size 1/| > ( S(FA(x)) where a size measure, e.g. set cardinality for classification.
5.2 Mini-ImageNNe
Mini- ImageNe 10 is smaller version of the ImageNet dataset for few-shot learning.
Setup. Mini-ImageNNet consists of 100 classes with 64 classes for training, 16 classes for calibration, and 20 classes for testing; each class has 600 images. Following standard setup, we consider five randomly chosen classes as one task and 5-way classification. training, we follows 5-shot 5-way learning, considering M 800 training task distribution randomly drawn from the (54) possible tasks. In calibration, we have possible tasks, and use 5 shots for adaptation and 500 shots for calibration (i.e., 25 and 2500). In evaluation, we have 50 test task datasets randomly drawn from the (5) possible tasks and use shots from each of 5 classes for adaptation and 100 shots from each 5 classes for evaluation.
500 calibration task datasets randomly drawn from the (20)
Results. Figure shows the prediction set error and size of the various approaches in box plots. Whiskers each box plot for the error cover the range between the 10-th and 90-th percentiles of the empirical error distribution, while whiskers in each box plot for the size represents the minimum and maximum of the empirical size distribution. The randomness of error and size is due to the randomness of the augmented calibration (S, .A) and test adaptation set A; but since 8 = 10 the randomness mostly due to the adaptation set.
The prediction set error of the proposed approach is below the desired level E = 0.1 at least a fraction 1 a 0.9 of the time. This supports that the proposed prediction set satisfies the meta PAC criterion. However, PS and Meta-CP do not empirically satisfy the meta PAC criterion, and PS-Test too conservative. particular, Meta-CP does not empirically control the randomness due to test distribution. To make this point precise, Figure Sc shows prediction set error distribution over different test distributions given fixed calibration dataset. As can be seen, the proposed Meta-PS approach empirically satisfies the error criterion at least fraction 1 0.9 of the time (as

---

prediction set error
prediction set set- size
0.15
0.10
0.05
0.00
PS-Test Meta-CP Mata-PS
PS-Test Meto Meta-PS
(a)
(b) Size
Figure 4: Prediction set error and size FewRel. Parameters are N 500, 2500, t 25, E 0.1, a = 0.1, = 10-5 for Meta-PS and E = 0.1, 10 for other methods.
shown in the whiskers), but Meta-CP does not empirically control Figure demonstrates that the proposed Meta-PS produces smaller prediction sets compared to the PS-Test approach that also satisfics the E error constraint.
5.3 FewRel
FewRel 16 is an entity relation dataset, where each example is the tuple of the first and second entities in sentence along with their relation as a label.
Setup. FewRel consists 100 classes, where 64 classes are used for training and 16 classes are originally used validation; each class has 700 examples. The detailed setup for training, calibration, and test are the same as those mini-ImageNee, except that the test task distributions are randomly drawn from the original validation split.
Results. Figure presents the prediction set error and size the approaches. The trend the results is similar to the mini-ImageNet result. Ours empirically satisfies the desired prediction set error specified by e with empirical probabilities of at least 1 - a over the test adaptation set and 1 over the (augmented) calibration data. In contrast, the other approaches either do not empirically satisfy the meta PAC criterion or are highly conservative. Figure bal also confirms that the proposed approach empirically controls the error with probability least
the randomness in the test cataset.
5.4
CDC Heart Dataset
The CDC Behavioral Risk Factor Surveillance System consists of health-related telephone surveys started in 1984. The survey data is collected from US residents. We the data collected from 2011 to 2020 and consider predicting the risk of heart attack given other features (e.g., level of exercise weight). We call this curated dataset the CDC Heart Dataset. See Appendix D.4 for the details of the experiment setup.
Setup. The 10 years of the CDC Heart Dataset consists of 530 task distributions from various US states. We consider data from 201 1-2014 as the training task distributions, consisting of 212 different tasks and 1,805,073 labeled examples, and data from 2015-2019 as calibration task distributions, consisting of 265 different tasks and 2,045,981 labeled examples. We use the data from 2020 as test task distribution, consisting of 53 different tasks and 367,511 labeled examples. We M 200, N 250, n = 3000, and = 10; see Appendix D.4 for the details.
Results. Figure 5 includes the prediction set error and size of each approach. The trend is as before. The proposed Meta-PS empirically satisfies the & below of the 0.1 line), while PS and Meta-CP CP violate this constraint. Meanwhile, PS-Test conservatively satisfies it. As before, Figure 6b empirically justifies that the proposed approach controls the prediction set error due to the randomness over the test adaptation data.
constraint (i.e, the top of the whisker
6 Conclusion
We propose PAC prediction set algorithm for meta learning, which satisfies PAC property tailored to meta learning setup. The efficacy of the proposed algorithm demonstrated four datasets across three application domains. Specifically, observe that the proposed algorithm finds

---

2,00
== 0.10
1.75
1.50
prediction set
1.25
prediction
1.00
0.15
0.75
0.10
0.50
0.05
0.25
0.00
0.00
P5-Test
Meta-CP Meta-PS
PS-Test Mata-CP Meta-P5
(a) Error
(b) Size
Figure 5: Prediction set error and size on CDC Heart Dataset. Parameters are N 250, 3000,
t 10, 0.1, a 0.1, å = 10 for Meta-PS and E 0.1, 10-5 5 for other methods.
Meta-CP
prediction set error
Meta-PS
0.10
8
0.10
0.05
0.00
20
calibration distribution Index
(a) FewRel
Meta-CP Meta-PS
prediction Set error
0.175
0.150
E 0.10
0.125
0.100
0.075
0.050
0.000
ca Calibration distribution index
(b) CDC Heart Dataset
Figure Meta-PS and Meta-CP prediction set error for various calibration sets. Given one calibration set (i.e., fixed calibration distribution index), the box plot with whiskers represents the (c, --guarrtteee The proposed Meta-PS satisfies the & = 0.1 constraints at least 1 - a = 0.9 of the time, as the whisker is below the dotted line indicating However, Meta-CP does not satisfy this constraint, showing that the proposed approach can control the correctness on future tasks.
prediction set that satisfies specified PAC guarantee, while producing small set size. A limitation of the current approach is that requires enough calibration datapoints to satisfy the PAC guarantee, see [3] for analysis. A potential societal impact is that user of the proposed algorithm might misuse the guarantee without proper understanding of assumptions; see Appendix for details.
Acknowledgements
This work was supported in part by DARPA/AFRL FA8750-18 187750-8-C--0090. ARO W911NF-20. 1-0080, NSF TRIPODS 1934960, NSF DMS 2046874 (CAREER). NSF-Simons 2031895 (MoDL). Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Air Force Research Laboratory (AFRL), the Army Research Office (ARO), the Defense Advanced Research Projects Agency (DARPA), or the Department of Defense, the United States Government.
10

---

References
[1] Samuel S Wilks. Determination of sample sizes for setting tolerance limits. The Annals of Mathematical Statistics, 12(1):91-96, 1941.
[2] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning random world. Springer Science & Business Media, 2005.
[3] Sangdon Park, Osbert Bastani, Nikolai Matni, and Insup Lee. Pac confidence sets for deep neural networks via calibrated prediction. In International Conference on Learning Representations, 2020.
[4] Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-fiue risk risk-controlling prediction sets. arXiv preprint arXiv:2101.02703 2021.
[5] Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in Neural Information Processing Systems, 32:2530- 2540, 2019.
[6] Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. PAC prediction sets under covariate shift. In International Conference on Learning Representations, 2022.
[7] Hongxiang Qiu, Edgar Dobriban, and Eric Tchetgen Tchetgen. Distribution-free prediction sets adaptive to unknown covariate shift. arXiv preprint urXiv:2203.06/26, 2022.
[8] Isaac Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift, 2021.
[9] Jurgen Schmidhuber. Evolutionary Principles in Relf-Referential Learning. On Learning now to Learn: The Metit--Met--Mett--Hooo Diploma thesis, Technische Universitat Munchen, Germany, 14 May 1987.
[10] Oriol Vinyals, Charles Blundell, Timothy Lillicrap. Daan Wierstra, et al. Matching networks for one shot learning. In Advances in neural information processing systems, volume 29, 2016.
[11] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
[12] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. International conference on machine learning, pages 1126-1135. PMLR, 2017.
[13] Kwonjoon Lee, Subhransu Maji. Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages (0657-10665 2019.
[14] Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Few-shot conformal prediction with auxiliary tasks, 2021.
[15] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. Proceedings of the International Conference on Learning Representations, 2019.
[16] Xu Han, Hao Zhu, Pengfei Yu, Ziyun Wang, Yuan Yao, Zhiyuan Liu, and Maosong Sun. FewRel:
A large-scale supervised few-shot relation classification dataset with sate-of-theeart evaluation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4803-4809, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.
[17] Centers for Disease Control and Prevention (CDC). Behavioral Risk Factor Surveillance System. https://ww/ cdc. wacc.govbbbr gov/brfss. http//nnnallleee cacell__ata/aaeee hal___dttaaanaaaddae htm 1984.
[18] A Gammerman, V Vovk, and V Vapnik. Learning by transduction. In Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence, pages 148-155, 1998.
[19] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pages 345-356. Springer, 2002.
[20] Robin Dunn, Larry Wasserman, and Aaditya Ramdas. Distribution-free prediction sets for two-layer hierarchical models. Journal of the American Statistical Association, pages 1-12, 2022.
11

---

[21] Vladimir Vovk. Conditional validity of inductive conformal predictors. Machine learning. 9202-3):349-376, 2013.
[22] I. Guttman. Statistical Tolerance Regions:
Classical and Bayesian. Griffin''s statistical mono- graphs & courses. Hafner Publishing Company, 1970.
[23] Charles Clopper and Egon S Pearson. The use confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-4)) 1934.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section +
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? (Yes) See Section
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No] Code will be released once accepted along with data and precise instructions to run it.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and a
(c) Did you report error bars (e.g., with respect the random seed after running periments multiple times)? [Yes] We use box plots to represent the randomness on error.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section D.I
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Section D.2
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you'l 'e
using/curating? [Yes] See Section D.2]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] See Section D.2
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "zHj_Z8ahMtK", "reviewer": "Reviewer_4tu2", "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.", "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", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\nThis 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. \n\nQuality:\nThis paper is technically sound and theoretical analysis is clear.\n\nClarity:\nThis paper is easy to follow.\n\nSignificance: \nThis paper provides insights to conformal prediction in meta learning setting.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "wR0SLzl02u4", "reviewer": "Reviewer_MYhn", "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. ", "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?\n2. The authors select PS-Binom to estimate \\tau. Do different estimators make difference in the performance? \n3. 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. \n2. Only one meta-model, prototypical network, is applied as a score function to evaluate the proposed method. \n3. The notations are very confusing, especially those applied for the score function, and prediction set. \n[1] Park, Sangdon, et al. \"PAC confidence sets for deep neural networks via calibrated prediction.\" arXiv preprint arXiv:2001.00106 (2019).", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed method is guaranteed by PAC bound. \n\nWeaknesses:\n1. The paper is not presented in a good way. The notation is very confusing and misleading in general.\n2. 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.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vqWJMpkgEiK", "reviewer": "Reviewer_TeH4", "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).\n\n[1] Few-shot conformal prediction with auxiliary tasks. https://arxiv.org/abs/2102.08898.", "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?\n - 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!", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nApart 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 \n1. On average over the random draw of calibration tasks that are used to choose this threshold...\n2. and on average over the random choice of task that is used to evaluate this threshold...\n3. and on average over predictions the model makes using this threshold on the new task...\n4. The prediction set contains the correct label.\n\n(Where we can replace \"average\" with high probability $1-\\delta$, $1-\\alpha$, $1-\\epsilon$.)\n\nI 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).\n\nOn to a few high-lighted strengths...\n\n- The theoretical setting is appealing, and a reasonable and useful extension to Meta-CP (as stated above). \n- 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). \n- Empirical results seem strong.\n\nAnd a few weaknesses...\n\n- 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.\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "j-MaVS3jmgo", "reviewer": "Reviewer_s7jQ", "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.\n", "questions": "Please refer to weaknesss above.", "limitations": "Yes, the authors have addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n\n* The paper is well-written.\n* The proposed method is reasonable with theoretical analysis.\n* Experiments on various domain and datasets are compared.\n\n\nWeakness:\n\n\n\n* For reusing the same meta prediction set parameter after adaptation, would be better if the meta predictions set parameters are also adapted?\n* 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).\n* 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.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MD7dNsjUrfm", "reviewer": "Reviewer_e4fH", "summary": "POST DISCUSSION:\n\nThe authors addressed most of my issues about readability and the attribution problem, so I have increased my score to a weak accept.\n\nMy final assessment is as follows:\nI believe the proofs are correct, and the related work is correct.\nI 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.\n\nI 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!\n\n_____________\nThis 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.", "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.)", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: I the technical results are clearly correct. The experiments are comprehensive.\n\nWeaknesses:\n\n(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.\n\n(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.\n\n(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. \n\n(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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept