Batch Multivalid Conformal Prediction
Authors: Christopher Jung
Georgy Noarov
Ramya Ramalingam
Aaron Roth
Venue: ICLR 2023 poster (2023)
Keywords: Conformal prediction
multicalibration
uncertainty quantification

Abstract: We develop  fast distribution-free conformal prediction algorithms for obtaining multivalid coverage on exchangeable data in the batch setting. Multivalid coverage guarantees are stronger than marginal coverage guarantees in two ways: (1) They hold even conditional on group membership---that is, the target coverage level $1-\alpha$ holds conditionally on membership in each of an arbitrary (potentially intersecting) group in a finite collection $\mathcal{G}$ of regions in the feature space. (2) They hold even conditional on the value of the threshold used to produce the prediction set on a given example. In fact multivalid coverage guarantees hold even when conditioning on group membership and threshold value simultaneously.

We give two algorithms: both take as input an arbitrary non-conformity score and an arbitrary collection of possibly intersecting groups $\mathcal{G}$, and then can equip arbitrary black-box predictors with prediction sets.  Our first algorithm is a direct extension of quantile regression, needs to solve only a single convex minimization problem, and produces an estimator which has group-conditional guarantees for each group in $\mathcal{G}$. Our second algorithm is iterative, and gives the full guarantees of multivalid conformal prediction: prediction sets that are valid conditionally both on group membership and non-conformity threshold. We evaluate the performance of both of our algorithms in an extensive set of experiments. 

Under review as a conference paper at ICLR 2023
BATCH MULTIVALID CONFORMAL PREDICTION
Anonymous authors Paper under double-blind review
ABSTRACT
We develop fast distribution- conformal prediction algorithms for obtaining multivalid coverage on exchangeable data in the batch setting. Multivalid cover- age guarantees are stronger than marginal coverage guarantees in two ways: (1) They hold even conditional on group membership-ther is, the target coverage level 1 a holds conditionally on membership in each of an arbitrary (potentially intersecting) group in a finite collection G of regions in the feature space. (2) They hold even conditional on the value of the threshold used to produce the prediction set given example. In fact multivalid coverage guarantees hold even when conditioning on group membership and threshold value simultaneously.
We give two algorithms: both take input arbitrary non-conformity score and an arbitrary collection of possibly intersecting groups G, and then can equip ar- bitrary black-box predictors with prediction sets. Our first algorithm Bat ch GCGP is a direct extension of quantile regression, needs to solve only a single convex minimization problem, and produces an estimator which has group-conditional guarantees for each group in G. Our second algorithm Bat chMVe is iterative. and gives the full guarantees of multivalid conformal prediction: prediction sets that are valid conditionally both on group membership and non-conformity thresh- old. We evaluate the performance of both of our algorithms in an extensive set of experiments.
INTRODUCTION
Consider an arbitrary distribution 'D over a labeled data domain 2 x y. A model any function h : X + y for making point predictions. The traditional goal of conformal prediction in the "batch" setting is to take a small calibration dataset consisting of labeled examples sampled from D and use it endow arbitrary model h X' - Y' with prediction sets Tx(x)) Y that have the property that these prediction sets cover the true label with probability for some target miscoverage rate Pr(z.a)~Dyy guarantee because the probability is taken over the randomness of both and y. without conditioning on anything. In the batch setting (unlike in the sequential setting), labels are available when the prediction sets are deployed. Our goal in this paper is to give simple, practical algorithms in the batch setting that can give stronger than marginal guarantees - the kinds of multivalid guarantees introduced by Gupta et al. (2022); Bastani et al. (2022) in the sequential prediction setting.
a marginally This is marginal coverage
[xx=)] = 1
Following the literature on conformal prediction (Shafer and Vovk, 2008), our prediction sets are parameterized by an arbitrary non-confommit score $ 2 - IR defined as a function of the model h. Informally, smaller values of 8n (x, y) should mean that the label y "conforms" more closely to the prediction h(x) made by the model. For example, in a regression setting in which y R. the simplest non-confornity score is 8), (x, = (x()) - y/- By now there is a large literature giving more sophisticated non-conformity scores for both regression and classification problems- see Angelopoulos and Bates (2021) 1) for an excellent recent survey. A non-conformity score function st. (z. y) induces distribution over non-conformity scores, and if is the 1 quantile of this r] <]
a), then defining prediction sets as T (x) = (y sy, (2, y) S 5] gives 1-a marginal coverage. Split conformal prediction (Papadopoulos et al., 2002;
distribution (i.e. Pr( (2, (z,y) y) I
Lei et al., 2018) simply finds a threshold 7 that is an empirical 1 quantile the calibration set, and then uses this to deploy the prediction sets T (a) defined above. Our goal is to give stronger coverage guarantees, and to do so, rather than learning single threshold 7 from the calibration set,

---

Under review as a conference paper at ICLR 2023
will learn a function f X ++ R mapping unlabeled examples to thresholds. Such mapping induces prediction sets defined as follows: Th (x) {y sn (z., y) f())
Our goal is to find functions f x - IR that give valid conditional coverage guarantees of two sorts. Let G be an arbitrary collection of groups: each group g 9 is some subset of the feature domain g E 2 about which we make no assumption and we write g(x) = to denote that æ is a member of group g. An example might be member of multiple groups in G. We want to learn a function f that induces group conditional coverage guarantees-ice such that for every E G: Pr(a.y)~Dly E Ti (=))((r)) = 1] 1 - a. Here we can think of the groups as representing e.g. demographic groups (broken down by race, age, gender, etc) in settings in which we are concerned about fairness, or representing any other categories that we think might be relevant to the domain at hand. Since our functions f now map different examples z to different thresholds f(x). we also want our guarantees to hold conditional on the chosen threshold-wee which call threshold calibrated guarantee. This avoids algorithms that achieve their target coverage rates by overcovering for some thresholds and undercovering with others for example, by randomizing between full and empty prediction sets. That is, we have: Pr(m.y)=Dl E TV (=)]g(æ) = 1, f(x) = = a simultaneously for every g E G and every r E R. If f is such that its corresponding prediction sets Ty (z) satisfy both group and threshold conditional guarantees simultancously, then we say that it promises full multivalid coverage.
1.1 OUR RESULTS
We design, analyze, and empirically evaluate two algorithms: one for giving group conditional guarantees for an arbitrary collection of groups G, and the other for giving full multivalid coverage guarantees for an arbitrary collection of groups G. We give PAC-style guarantees (Park et al., 2019), which means that with high probability over the draw of the calibration set, our deployed prediction sets have their desired coverage properties on the underlying distribution. Thus our algorithms also offer generalization theorems under the assumption that the data is drawn i.i.d. from some distribution, but note that De Finetti's theorem (Ressel, 1985) implies that our analysis carries over to data drawn from any exchangeable distribution (see Remark C.1).
coverage" in the sense of Bian and Barber (2022). We prove our
Group Conditional Coverage: BatchGCP We first give exceedingly simple algorithm BatchGCP (Algorithm 1) to find model f that produces prediction sets T that have group conditional (but not threshold calibrated) coverage guarantees. We consider the class of functions = [fs F=
A RRBlI: each fa E F is parameterized by a vector À E R and takes value: fa(z) = fo(x) Egeg-g(e)=1 Ag. Here fo is some arbitrary initial model. Our algorithm simply finds the parameters X that minimize the pinball loss of fx(.. This is a -ddimensional convex optimization problem and so can be solved efficiently using off the shelf convex optimization meth- ods. We prove that the resulting function (x) guarantees group conditional coverage. This can be viewed as an extension of conformalized quantile regression (Romano et al., 2019) which is also based on minimizing pinball loss. It can also be viewed as an algorithm promising "quantile mul- tiaccuracy". by analogy to (mean) multiaccuracy introduced in Hébert-Johnson et al. (2018); Kim et al. (2019), and is related to similar algorithms for guaranteeing multiaccuracy (Gopalan et al., 2022b). Here pinball loss takes the role that squared loss does in (mean) multiaceuracy.
Multiyalid Coverage: BatchMVP We next give a simple iterative algorithm BatchMVP (Algo- rithm 2) to find model f that produces prediction sets Th that satisfy both group and threshold conditional guarantees simultaneously - i.e. full multivalid guarantees. iteratively finds groups G and thresholds such that the current model fails to have the target coverage guarantees conditional on g(x) = and f(x) = т, and then "patches" the model so that it does. We show that each patch improves the pinball loss of the model substantially, which implies fast convergence. This can be viewed as an algorithm for promising "quantile multicalibration" and is an extension of related algorithms for guaranteeing mean multicalibration (Hébert-Johnan et al., 2018), which offer similar guarantees for mean (rather than quantile) prediction. Once again, pinball loss takes the role that squared loss takes in the analysis of mean multicalibration.
2

---

Under review as a conference paper at ICLR 2023
Empirical Evaluation We implement both algorithms, and evaluate them synthetic prediction tasks, and on 10 real datasets derived from US Census data from the 10 largest US States using the "Folktables" package of Ding al. (2021). In synthetic experiments, ditional coverage with respect to synthetically defined groups that are constructed to be correlated with label noise. On Census datasets, aim to ensure coverage on population groups defined by reported race and gender categories. We compare our algorithms to two other split conformal predic- tion methods: naive baseline which simply ignores group membership. and uses a single threshold, and the method of Foygel Barber et al. (2020), which calibrates a threshold T for each group g G, and then on a new example z, predicts the most conservative threshold among all groups belongs to. We find that both of our methods obtain significantly better group- woip-wise coverage and threshold calibration than the baselines we compare to. Furthermore, both methods are very fast in practice, only taking few seconds to calibrate on datasets containing tens of thousands of points.
measure group
We have discussed the most closely related work; but see Appendix A for an extended discussion of additional related work.
2 PRELIMINARIES
We study prediction tasks over a domain = y. X' denotes the feature domain and y the label domain. We write G C 2* to denote collection of subsets of X' which we represent as indicator functions g X - {0, 1}. The label domain might e.g. be real valued (Y' = -he regression setting, or consist of some finite unordered set-the multiclass classification setting.
Suppose there is a fixed distribution D E AZ, Given such a distribution, we will write Dx to denote the marginal distribution over features: Dx E A induced by D. We will write (z A to denote the conditional distribution over labels induced by D) when we condition on a particular feature vector x. We sometimes overload the notation and write D(x)= Dy(x).
Our uncertainty quantification is based on a bounded non-conformity score function s: X'X R. Non-conformity score functions generally defined with respect to some model h which is why in the introduction we wrote 8) but our development will be entirely agnostic to the specifics of the non-conformity score function, and so we will just write for simplicity. Without loss of generality, we assume that the scoring function takes values in the unit interval: s(x, y) E [0, 1] for any x e X and y V. Given a distribution D over = X y and a non-conformity score function s, we write S to denote the induced joint distribution over feature vectors J and corresponding non-conformity scores sxx y). Analogously to our D(x) notation, we write S(x) to denote the non-conformity score distribution conditional on a particular feature vector x. Given a subset of the feature space B C X, we write B to denote the conditional distribution on non-conformity scores conditional on x E B. Finally, we assume that all non-conformity score distributions (zx) are continuous, which simplifies our treatment of quantiles - note that if this is not the case already, can be enforced by perturbing non-conformity scores with arbitrarily small amounts of noise from continuous distribution.
Definition 2.1. For any q E [0, 1], we say that T a q-quantile of (continuous) nonconformity score distribution S if PT(a,s)~s(s I <| r]= =4
Our convergence results will be parameterized by the Lipschitz parameter of the CDF of the under- lying nonconformity score distribution. Informally speaking, a distribution with a Lipschitz CDF cannot concentrate too much of its mass on interval of tiny width. Similar assumptions are com- monly needed in related work, and can be guaranteed by perturbing non-conformity scores with noise see e.g. the discussion in (Gupta et al., 2022; Bastani et al., 2022).
Definition 2.2. A conditional nonconformity score distribution S(x) p-Lipschitz if we have Pra-S(w)(8 < r' - Pre-SSta)ss Σ r] I p(T' - -T) for all < < < 1. A nonconformity score distribution S is p-Lipschitz for each x E X. S(x) is p-Lipschitz
If we could find a model f : X'' + [0. 1] that on each input x outputs a value f(x) that is a q-quantile of the nonconformity score distribution S(z), this would guarantee true conditional coverage at rate q: for every x, Pr,, [y E T [x)] impossible, our aim will be to train models ff that allow us to make similar claims- - not conditional on every x, but conditional facilitate learning models of with guarantees conditional on their output values, we will learn models R(() < cc.
q, where T
{y s(x, u) < f())). As this is generally
membership of in some group g and the value of fz). To
whose range R(ʃ)= {f(x) x E X) has finite cardinality
3

---

Under review as a conference paper at ICLR 2023
3 ALGORITHMS
3.1
ALGORITHMIC PRELIMINARIES
In this section we establish lemmas that will be key the analysis of both of the algorithms we give. Both of our algorithms will rely on analyzing pinball loss as potential function.
Definition 3.1. The pinball loss at target quantile for threshold т and nonconformity score is
Lg(T, - (s ()q 1[s +] (T s) q) 1[s T]
We write PB (J) distribution S. When quantile and/or distribution S is clear, we write PB, PBg. and/or PBS.
[T)([()), 8)] for a model f X [0, 1] and nonconformity score
(2.3)~5
well known that pinball loss is minimized by the function that predicts for each æ the target quantile of conditional score distribution given but we will need a more refined set of state- ments. First we define model's marginal quantile consistency error:
Definition 3.2. A q-quantile predictor f X R has marginal quantile consistency error if ( $ f(x)] - g) = a. If a = O, we say that f satisfies marginal q-quantile consistency.
Informally, we will need the pinball loss to have both progress and an "anti aanti-progress" property: If model f is far from satisfying marginal quantile consistency, then linearly shifting it so that it becomes marginal quantile consistent should reduce pinball loss substantially. Conversely, marginal quantile consistent, then perturbing it slightly should not increase pinball loss substantially. The next lemma establishes these, under the assumption that the underlying distribution is Lipschitz.
is
Lemma 3.1. Fix any nonconformity score distribution S that p-Lisschitz. Fix any model f : X' + R that has marginal quantile consistency error a with respect to target quantile q, and let fx()) = f(x) + A with A chosen such that f is marginal quantile consistent at quantile 9. Then
a²
a²
+ -a/A|+
2p
2p"
We now define what will be a basic building block of our iterative algorithm for obtaining multivalid coverage, and of the analysis of our algorithm for obtaining group conditional coverage. is simple "patch" operation on model, that shifts the model's predictions by a constant term A only on those examples x that lie some subset of the feature space:
Definition 3.3 (Patch Operation). Given model f. subset B C, and value A E R define the patched model f' = Pf B, A) to be such that
(x) ((x A E and f'(x)= [(x) otherwise.
We next show that if we have model f. and we can identify large region B on which it is far from satisfying marginal quantile consistency, then "patching" the model so that satisfies marginal quantile consistency on S' substantially improves its pinball loss.
Lemma 3.2. Given some predictor f X R, suppose we have a set points B C X with
(
Pr f(x)/x B] B] ) za and A argmin
Pr |x BI (a.s)~s
Pr [s S f(x) + AAI BJ -q
AVER [0.a)~
Then, S is continuous and p-Lipschitz, Patch(f, f, B,A) has PB) PBS(S
3.2 BATCEGCP: OBTAINING GROUP CONDITIONAL GUARANTEES
We now give an extremely simple algorithm Bat (Batch Group-Conditional Predictor) that obtains group conditional (but not threshold calibrated) prediction sets. BatchGCP only needs to solve a single closed-fore convex optimization problem. Specifically, Algorithm takes as input an arbitrary threshold model f and collection of groups G, and then simply minimizes pinball loss all linear combinations of f and the group indicator functions E G. This a quantile-analos of similar algorithm that obtains group conditional mean consistency (Gopalan al., 2022b).

---

Under review as a conference paper at ICLR 2023
Algorithm 1: BatchhCP(J.9. D)
Let X be solution the optimization problem:
La (f(x; s(2.)))) where f(x;A) f(z) 1 g(x)
argmin,
(..
9EG
Output (x;
Theorem 3.1. For any input model f. groups 9, and q E [0, 1], Algorithm returns f(r; X²) with y (x))())))) =1] = for every g E g,
Pr
(ma))D
where (x) (y: (:: ((, & f(x; X²)) Furthermore, (B( S (J)
The analysis is simple: if the optimal model f(z, X²) did not satisfy marginal quantile consistency
on some g E G. then by Lemma 3.2, patch operation on the set B(g) = f g(x) = =1 would further reduce its pinball loss. By definition, this patch would just shift the model parameter X and yield model fzx, X²) for X * X", falsifying the optimality of f(x, X*) among such models.
3.3 BATCEMVP: OBTAINING FULL MULTIVALID COVERAGE
In this section, we give simple iterative algorithm BaM (Batch Multivalid Predictor) that trains threshold model that provides full multivalid coverage - i.e. that produces prediction sets (2) that are both group conditionally valid and threshold calibrated. To do this, we by defining quantile multicalibration, quantile prediction analogue of (mean) multicalibration defined Héhert-Johnson et (2018); Gopalan et (2022a).
Definition 3.4. The quantile calibration error of q-quantile predictor f X.X- - [0, on group is:
Q(f.) = Σ Pr [f(x) = vlg(z) = 11(1 Pr is f(x)]f(z) = v ( = 11)
vER(S) (I,,))
(H.6)~
We say that f is a-approximately q-quantile multicalibrated with respect to group collection g if a
Q(f.)) < P)(c.a)=s(((=)= =
for every g G.
Conditional on membership in each group y. the quantile multicalibration error gives bound on the expected coverage error when conditioning both on membership y and on a predicted threshold of f()) in expectation over In particular, it implies (and is stronger than) the following simple worst-case (over g and v) bound on coverage error conditional on both g(x) = 1 and f(z) = V:
Claim 3.1. If f is a-approximately quantile multicalibrated with respect and q. then
Va
[ E TT((()))())) f(x) = (z.g)>D
Pr
for E GGGE R().
v (((
Algorithm 2: Batcch/accfff...c.. 9. S.p.S,m)
Initialize f = 0, and define fo as fo(z) min |l f(x) for æ E X.
while fO is not a-approximately q-quantile multicalibrated with respect to G do
Let B, = (x: fe(x)) vt, gr (x) = 1}, where:
(vr.gt) E argmax Pr [f((z) (.g(z) =1] 11((-- (M.)) (s.s)
Pr (() = (T.S)
Let:
A = argmin
Pr [s < f((x) + Air Bd] (2,5)~
Ae
Update f(+1 +- Patch (fr, B,, A,) and t
Output ft.
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2 is simple: Given an initial threshold model f. collection of groups G, and target quan- tile q. it repeatedly checks whether its current model fe satisfies a-approximate quantile multicali- bration. If not, it finds group I: and threshold 2 such that ft predicts a substantially incorrect quantile conditional on both memhership of x in St and on ft(x) 1/ such a pair is guaranteed to exist if fa is not approximately quantile multicalibrated. It then fixes this inconsistency and produces a new model fr+1 with patch operation up to a target discretization parameter m which ensures that the range of f++1 does not grow too large. Under the assumption that the non-conformity score distribution is Lipschitz, each patch operation substantially reduces the pinball loss of the current predictor, which ensures fast convergence to quantile multicalibration.
Theorem 3.2. Suppose S is p-Lipschitz and continuous, and m 80² After T S rounds, Algorithm BatchMvP([ q, 9, p,,. S,S.m) returns frr such that
32p² a² many
1. PB (fr) s (B) -T -
32p3.
2. fr is a-approximately quantile multicalibrated with respect to G and q. In particular. via Claim 3.1, we have for every g E and v E R(f),
Va
Pr [V T (1))g(()))))) = 1, (x.g)>>
(Pr(aa)=ssgle)) = (T((z
OUT OF SAMPLE GENERALIZATION
We have presented BatchGCP (Algorithm 1) and BatChMVP (2) as if they have direct access to the true data distribution D. In practice, rather than being able to directly access the distribution, only have finite calibration set D (I;; y=)==1 of n data points sampled iid. from D. In this section, we show that if we run our algorithms on the empirical distribution over the sample D D= (Ia: y1) Y= then their guarantees hold not only for the empirical distribution over 7 but also with high probability - for the true distribution D. We include the generalization guarantees for Bat chGC in Appendix C.3 and focus on generalization guarantees for Bat chMVP.
At a high level, our argument proceeds as follows (although there are a number of technical com- plications). For any fixed model f. by standard concentration arguments its in- and -ampple quantile calibration error will be close with high probability for a large enough sample size. Our goal is to apply concentration bounds uniformly to every model fr that might be output by our al- gorithm, and then union bound over all of them to get high probability bound for whichever model happens to be output. Towards this, we show how to bound the total number of distinet models that can be output
function of T. the total number of iterations of the algorithm. This is possible because at each round f, the algorithm performs a patch operation parameterized by a group 9t E G (where [g] < oo), a value 2 [1/m], and update value As [1/m] and thus only a finite number of models fi+1 can result from patching the current model fe. The difficulty is that our convergence analysis in Theorem 3.2 gives convergence guarantee in terms of the smoothness pa- rameter P of the underlying distribution, which will not be preserved on the empirical distribution over the sample D drawn from D. Hence, to upper bound the number of rounds run for, we need to interlcave our generalization theorem with our convergence theorem, arguing that each step-taken with respect the empirical distribution over D-we can be bounded by the smoothness parameter of the underlying distribution D.
algorithm can
we make progress that
We first prove a high probability generalization bound for our algorithm as function of the number of steps T it converges in. This bound holds uniformly for all T, and so can be applied as a function of the actual (empirical) convergence time T.
We let D = (I,, 2L denote our sample, S = (æi, 8(1; V/ P= our nonconformity score sample, and S5 denote the empirical distribution over S. When S is clear from the context, we just write S. Theorem 4.1. Suppose S is p-Lipschitz and S ~ S". Suppose BatchMVP(f. 9, G. Ss,m) (Algorithmm 2) runs for T rounds and outputs model fr. Then fr al a'-approximately q-quantile multicalibrated with respect to G on S with probability 1 5, where
3p² (In(
472T2 36
+ Tin
(1(g a²
12p²
4t 22
)
+ T In
$ o²
o' = a
36
2an
an

---

Under review as a conference paper at ICLR 2023
00
Figure Performance comparisons across different conformal prediction methods. Groupwise coverage is on the left, and mean prediction-set size by group is the right (averaged over 50 runs). Error bars show standard deviation.
We then prove worst-case upper bound on the convergence time T, which establishes a worst-case PAC style generalization bound in combination with Theorem 4.1. We remark that although the theorem contains large constant, in our experiments, our algorithm halts after small number of iterations T (See Sections 5 and D), and we can directly apply Theorem 4.1 with this empirical value for T.
Theorem 4.2. Suppose S is p-Lipschitz and continuous, m = 2a and our calibration set S S" consists of tid. samples drawn from S, where is sufficiently large: n 2 92928
[n 128." + Sp In p1 max g' 4n= a Then BatchMVP(J, a, q, 9, Ss.m) m) (Al-
gorithm 2) halts after T = 8p"
oz rounds with prob. 1 6.
Formal generalization arguments in Appendix C. Theorems 4.1, 4.2 are proved in Appendix C.4.
5 EXPERIMENTS
5.1 A SYNTHETIC REGRESSION TASK
We first consider a linear regression problem on synthetic data drawn from feature domain of 10 binary features and 90 continuous features, with each binary feature drawn uniformly at random, and each continuous feature drawn from normal distribution (0, o2). The 10 binary features are used to define 20 intersecting groups, each depending on the value of a single binary feature. An input's label is specified by an ordinary least squares model with group-dependent noise as:
y (0, x) / (0,02 2 I1e of where each term of is associated with one binary feature.
We set of for all i E [10]. So the more groups an input is a member of, the more label noise it has, with larger index groups contributing larger amounts of label noise.
We generate a dataset (Ir;y:)) of size 40000 using the above-deseribed model, and split it evenly into training and test data. The training data is further split into training data of size 5000 (with which train a least squares regression model f) and calibration data of size 15000 (with which calibrate our various conformal prediction methods). Given the trained predictor f. we use non-conformity score sxx y) = (=( yl. Next, we define the set of groups & {91, 92, ... (203 where for each j E 220, 9j {x E X L[(++1/22] =2 j + 1}. We run Algorithm 1 (BatchGCP) and Algorithm (BatchMVP ChMVP with m 100 buckets) to achieve group-conditional and full multivalid coverage guarantees respectively, with respect to G with target coverage 0.9. We compare the performance of these methods to naive split-conformal prediction (which, without knowledge of g, uses the calibration data to predict single threshold) and the method of Foygel Barber et al. (2020) which predicts a threshold for each group in g that an input x is part of, and chooses the most conservative one.
7

---

Under review as a conference paper at ICLR 2023
6063
0.000
4.000
5.000
00000
Figure 2: The left figure plots group-wiss calibration error (averaged over 50 runs), weighted by group size. Error bars show standard deviation. The right figure is a scatterplot of the number of points associated with each threshold-group pair (g, T.) against the average coverage conditional on that pair for all g G and all in grid, over all tested conformal prediction methods (consolidating results over all 50 runs). Target coverage is 0.9.
Figures 1 and 2 present results over 50 runs of this experiment. Notice that both BatchCCn and Bat achieve close the desired group coverage across all groups--ith BatchGCP achiev- ing nearly perfect coverage and BatchMVP sometimes deviating from the target coverage rate by much as 1%. In contrast, the method of Foygel Barber et al. (2020) significantly overcovers on nearly all groups, particularly low-noise groups, and naive split-conformal starts undercover- ing and overcovering on high-noise and low-noise groups respectively as the expected label-noise increases. Group-wise calibration error is high across all groups but the last using the method of Foygel Barber et al. (2020), and naive split-conformal has low calibration error on groups where in- clusion/excluss reflects less fluctuation in noise, and higher calibration error in groups where there much higher fluctuation noise based on inclusion. Both Bat chGCP and Bat chMVP have lower group calibration errors interestingly, BatchGCP appears to do nearly well ChMV in this regard despite having no theoretical guarantee on threshold calibration error. A quantile mul- groups 9 and thresholds т, that
ticalibrated predictor must have low coverage еπтоr conditional appear frequently, and may have high coverage error for pairs that appear infrequently- behavior that we see in Ba t chMVP in Figure 2. On the other hand, for both naive split conformal prediction and the method of Foygel Barber et al. (2020), we see high mis-coverage error even for pairs (g, T;) containing large fraction of the probability mass.
We fix the upper-limit of allowed iterations T for ChMC to 1000, but typically the algorithm converges and halts in many fewer iterations. Across the 50 runs of this experiment, the average number of iterations T taken to converge was 45.54 + 14.77.
5.2 AN INCOME PREDICTION TASK ON CENSUS DATA
We also compare our methods to naive split conformal prediction and the method of Foygel Barber et al. (2020) on real data from the 2018 Census American Community Survey Public Use Microdata, compiled by the Folktables package (Ding et al., 2021). This dataset records information about individuals including race, gender and income. In this experiment, we generate prediction sets for a person's 's income while aiming for valid coverage intersecting groups defined by race and gender.
The Folktables package provides datasets for all 50 US states. We run experiments on wide datasets: for each state, we split it into 60% training data Derain for the prcmme-predictor, 20% calibration data Deatib to calibrate the conformal predictors, and 20% test data Drest- After training the income-por preedcctr on D Dirain- are 9 provided codes for race and 2 codes for sex (1. Male, 2. Female) in the Folktables data. We
the non-conformity score s(x, y) = [f(x) y). There
I. White alone, 2. Black or African American alone, 3. American Indian alone, 4. Alaska Native alone, 5. American Indian and Alaska Native tribes specified; or American Indian or Alaska Native, not specified and no other races, 6. Asian alone, 7. Native Hawaiaan and other Pacific Islander alone, 8. Some Other Race alone, Two More Races.
8

---

Under review as a conference paper at ICLR 2023
grives
097
500R
2006
Figure 3: Performance across different conformal prediction methods on Folktables California data. Groupwise coverage is on the left, and mean prediction-set sizes for each group are the right (averaged over 50 rounds). Error bars show standard deviation.
0.00
0/00
0.000
4.000
4.000
4.00
11000
Figure 4: The left figure plots group-wise calibration error, weighted by group size (averaged over 50 runs). Error bars show standard deviation. The right figure is scatterplot of the number of points associated with each threshold preshold-group pair (g.T:) T.) against the average coverage conditional on that pair for all g and all T; in a grid, all tested conformal prediction methods (consolidating results over all 50 runs). Target coverage is 0.9.
define groups for five out of nine race codes (disregarding the four with the least amount of data) and both sex codes. We run all four algorithms (naive split-conformal, the method of Foygel Barber et al. (2020), BatchGCP, and Ba BatchMVP with = 300 buckets) with target coverage q = 0.9.
We ran this experiment on the 10 largest states. Figure 3 and Figure present comparisons of the performance of all four algorithms on data taken from California, averaged over 50 different runs. Results on all remaining states are presented in Appendix D.2.
Just as in the synthetic experiments, both BatchGCP and BatchMVP achieve excellent coverage across all groups-in in fact now, we see nearly perfect coverage for both Bat chGCP and Bat chMVP, with Bat chGCP still obtaining slightly better group conditional coverage. In contrast, naive split- conformal prediction undercovers on certain groups and overcovers on others, and the method of Foygel Barber al. (2020) significantly overcovers some groups (here, group 4 and 7). The conservative approach also generally yields prediction sets of much larger size. We see also that Bat ChMVP achieves very low rates of calibration error across all groups, outperforming Bat ChGCP in this regard. Calibration error is quite irregular across groups for both naive split-conformal pre- diction and for the method of Foygel Barber al. (2020), being essentially zero certain groups and comparatively much larger in others. The average number of iterations T Bat ChMVP converged in was 10.64 1.12.
Reproducibility statement The full Python implementations of Bat chGCP and Bat can be found in the supplementary zip. Jupyter notebooks that implement each of our experiments

---

Under review as a conference paper at ICLR 2023
also included in the supplementary zip. For details on experiments, such as how generate the data, what conformal scores we use, how we instantiate Bat chMVP and BatchCCP, please see Section 5 and Appendix D, well as the corresponding Jupyter notebooks. Proofs of all theoretical results are included, either in the main body of the paper or the designated Appendices.
REFERENCES
Anastasios Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-fie uncertainty quantification. arXiv preprint arXiv:2107.07511 2021.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2020.
Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. Advances Neural Information Processing Systems, 2022.
Michael Bian and Rina Foygel Barber. Training-conditionns coverage for distribution-free predictive inference. arXiv preprint wrXiv22255.0364 2022.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Cynthia Dwork, Michael Kim, Omer Reingold, Guy N Rothblum, and Gal Yona. Learning from outcomes: Evidence-based rankings. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 106-125. IEEE, 2019.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 2020.
Ira Globus-Harris Varun Gupta, Christopher Jung, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Multicalibrated regression for downstream fairness. arXiv preprint arXiv:2209.07312. 2022.
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Om- nipredictors. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). für Informatik, 2022a.
Schloss
Parikshit Gopalan, Michael Kim, Mihir A Singhal, and Shengjia Zhao. Low-degree multicalibra- PMLR, 2022b.
tion. In Conference Learning Theory, pages
Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online Multi- valid Learning: Means, Moments, and Prediction Intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 12:1-82:24, 2022.
Úrsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cal- ibration for the coomputaiionall--deenfibbb masses. In International Conference on Machine Learning, pages 1939-1948, 2018.
Peter Hoff. Bayes-optimal prediction with frequentist coverage control. arXiv preprint arXiv:2105.14045, 2021.
Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra. Moment multi- calibration for uncertainty estimation. In Conference on Learning Theory, PMLR, 2021.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerryman- dering: Auditing and learning for subgroup fairness. International Conference on Machine Learming, pages 2564-2572, 2018.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich sub- group faimess for machine learning. In Proceedings of the Conference on Fairness, Accountabil- ity, and Transparency, pages 100-109, 2019.
10

---

Under review as a conference paper at ICLR 2023
Michael P Kim, Amirata Ghorbani, and James Zou. Multiaceuracy: Black-box post-processingg for fairness in classification. In Proceedings of the 2019 AAAT/ACM Conference on Al, Ethics, and Society, pages 247-254, 2019.
Jing Lei, Max Gelll,, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (233):094-1111 2018.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confi- dence machines for regression. In European Conference on Machine Learning, pages 345-356 Springer, 2002.
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, 2019.
Paul Ressel. De finetti-type theorems: an analytical approach. The Annals of Probability, 13(3): 898-922, 1985.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Ad- vances in neural information processing systems, 32, 2019.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2020a.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive cover- age. Advances in Neural Information Processing Systems, 33:3581-3591, 2020b.
Guy N Rothblum and Gal Yona. Multi-group agnostic pac learnability. In International Conference on Machine Learning, pages 9107-9115. PMLR, 2021.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(Mar):371-4211 2008
A ADDITIONAL RELATED WORK
Conformal prediction (see Shafer and Vovk (2008); Angelopoulos and Bates (2021) for excellent surveys) has seen a surge of activity in recent years. One large category of recent work has been the development of sophisticated non-conformity scores that yield compelling empirical coverage in various settings when paired with split conformal prediction (Papadopoulos et al., 2002; Lei al., 2018). This includes Romano et al. (2019) who give nonconformity score based on quantile gression, Angelopoulos et al. (2020) and Romano et al. (2020b) who give nonconformity scores designed for classification, and Hoff (2021) who gives nonconformity score that leads to Bayes optimal coverage when data is drawn from the assumed prior distribution. This line work is com- plementary to ours: give algorithms that can be used drop-in replacements for split conformal prediction, and can make use of any of these nonconformity scores.
Another line of work has focused on giving group conditional guarantees. Romano et al. (2020a) note the need for group-conditional guarantees with respect to demographic groups when fairness concern, and propose separately calibrating on each group in settings in which the groups are disjoint. Foygel Barber et al. (2020) consider the case of intersecting groups, and give an algorithm that separately calibrates on each group, and then uses the most conservative group-wise threshold when faced with examples that are members of multiple groups - the result is that this method systematically over-covers. The kind of "multivalid" prediction sets that we study here were first proposed by Jung et al. (2021) in the special case of prediction intervals: but the algorithm given by Jung et al. (2021), based on calibrating to moments of the label distribution and using Chebyshev's inequality, also generally leads to over-coverage. Gupta et al. (2022) gave theoretical derivation of an algorithm to obtain tight multivalid prediction intervals in the sequential adversarial setting, and Bastani et al. (2022) gave a practical algorithm obtain tight multivalid coverage in the general case also in the sequential adversarial setting. Although the sequential setting is more difficult in the sense that it makes no distributional assumptions, it also requires that labels be available after

---

Under review as a conference paper at ICLR 2023
predictions made at test time, in contrast to the batch setting that we study, in which labels available. Gupta et al. (2022) give an online-to- so-bbtch reduction that requires running the sequential algorithm large calibration set, saving the algorithm's internal state at each iteration, and then deploying a randomized predictor that randomizes over the internal state of the algorithm across all rounds of training. This is generally impractical for large datasets; in contrast we give direct, simple, deterministic predictor in the batch setting.
Our algorithms can be viewed learning quantile multiaccurate predictors and quantile multicali- brated predictors respectively - by analogy to multiaccuracy Kim et al. (2019) and multicalibration Hébert-Johnson et al. (2018) which are defined with respect to means instead of quantiles. Their analysis is similar, but with pinball loss playing the role played by squared error in (mean) multical- ibration. This requires analyzing the evolution pinball loss under Lipschitzness assumptions on the underlying distribution, which is a complication that does not arise for means. More generally, our goals for obtaining group conditional guarantees for intersecting groups emerge from the litera- ture on "multigroup" fairness e.g. (Kearns et al., 2018; Hébert-Johnson et al., 2018; Kearns et al., 2019; Rothblum and Yona, 2021; Dwork et al., 2019; Globus-Harn Harris et al., 2022)
B MISSING DETAILS FROM SECTION
B. MISSING DETAILS FROM SECTION 3.1
Lemma B.1. Fix any x E X and r E [0.
(f + s)
T,5) dI, ( d8(x) dS(x)
Pr
|sS fxx +
S())(
dr
[..1] dr
)~S(w)
Proof.
dl, (f()) +
/ dr [,(
1 d
E
S(x(
dr
/'' dr
Ly (f() ( sdds)(( [: d dr ( s)d)))(2)
+
(1 - (1-))d5(x) f- qdS(x)
Pr [s < 5|
snr((w)
Lemma 3.1. Fix any nonconformity score distribution S that is p-Lipschitz. Fix any model f
X R that has marginal quantile consistency error a with respect to target quantile q, and let f((x) f(z) + A with A chosen such that f is marginal quantile consistent at quantile Then
a² S PBC -
a²
aaAl +
2p
2p
Proof.
-P
1xx|0.1 L,(((x) + A)
ds)
- go (T. + TT,) SrS(dx, ds)
dr
dL)(f(z) + 3) S(dr, ds)dr
dr
/
[s S ((x) + - -0)
E
Pr
<anDx
(mn)(())
12

---

Under review as a conference paper at ICLR 2023
Pr 18 S ((x) + + dr (1.a)=s
3 S f(x) + T|dT - Aq
(2.3)~
where the fourth equality follows from Lemma B.I.
For convenience, write (T) - Pr(c,s)usls f(x + 7]. Note that
! (T /0 (2,0)
Pr S f(z) + rldr
Pr s I f()) - A + +ldd (2,0)~8
Pr is $ (x) + + (2,4)
Hs.p(T)d
as instead of sweeping the area under the curve from f(x to f(x)+ A, we can sweep the area under the curve from fz(x) f'(x) A because f'(z) f(z) +
Lemma B.2. Fix any conformity score distribution S that is p-Lipschitz A 0, and f X R. Then we have
(0) + (As, (O))
2p
$ S. Hs,
(HS..(A) - Hs)r(0))²
< (As))(A)A- -
2p
Proof. For simplicity write H(T) = HT. Note that H(T) is a non-negative function that increasing in T.
First, we find an upper bound the area. The maximum area that can be achieved when there's a linear rate of increase from y (()) to H(A) between I 0 and H(A)-H(() as depicted in Figure 5, The area measured via the integral can be calculated by subtracting the area of the triangle from the area of the rectangle from 0 to A and from y 0 to y = (A)).
Pr [s S f(x) + T|d7 (x.s)~
H(A)A- (H(A) (())²
2p
Now, we find a lower bound of the area. The area under the curve is minimized when there's linear increase from H (0) to H (A) between A 11A) H(0) and A. The area be calculated
p
the of the area of the rectangle from to x A and from y (()) and the area of the triangle.
100
Pr Is S 51(x) + T]dr
(5,s)~s
H(O) H(A) HH())
(H(A) H(O))
2p
13

---

Under review as a conference paper at ICLR 2023
H())
(())
H(A) H(O)
[[(A)-M())
Figure 5: Upper and lower bounding the local area under H. The max-area CDF curve is in dashed blue, the min-area CDF curve in solid purple
Case (i) A 0: We have ( and Hs,
(B) - PB)(f) S Hs.s (HHs)((A) -Hs,
Ag
2p
a²
2p
On the other hand,
PB,(F) - PB,(f) (0)) (As.r(A)
Hs. (0))² Aq
2p
a²
(g- a +
Aq
2p
a²
--aA+ +
2p
Case (ii) A < 0: We have we have Hs.r(A) = Hs. and Hs., = Hs,r((A) a+a
where A A,
we have
PB,(J) - -BB())BB------ =
Hs.r - AA
A'
Hs, 9A
(s)r( (Hs,r(A)
- Hs. (0))²) 92
2p
a²
2p
14

---

Under review as a conference paper at ICLR 2023
On the other hand, we have
%
A Hs. A
PB₂ -B (T) - aA
(A))' (HS
- -)ss)(0))))) )) -9A
2p
aa) + a²
2p
=A + a²
2p"
Lemma 3.2. Given some predictor f. R, suppose we have set of points B C X with
( Pr Is f(0)/2 BJ
Pr [x E B). (I,
za and A = argmin
Pr [s I f(x)) + 1 -
A'ER
(1,
Then, SB is continuous and p-Lipschitz, f Patch(f, B, A) has PB
PB के
Proof. Note that f's marginal quantile consistency error with respect to target quantile g as measured on S is
Pr (I,
[s S [(=)]
2 Pr(a.))~s( E
Also, since B is continuous, have
Pr (
|s S f(x)+A)
In other words, f' satisfies marginal quantile consistency for g as measured on S S.B. Applying Lemma 3.1 to SIB, we have
(B) - ()) Pr (xr E (PBB (PBS)B(()) - PB (f) (2,s)ms
Pr [xr E B] 2p Pr o B
(2,5)ms
2p
B.2 MISSING DETAILS FROM SECTION 3.2
Theorem 3.1. For any input model f, groups and q E [0, 1), Algorithum returns fax X²) with Pr y (x)))))))))=== = = for every g E G,
where s(x w) < fax; Xt)). Furthermore, PB (B((((())) PB.
g' g - i.. PI( [g (x((x) = 1] (Pr(s,))s($ I f(x)lg((x) = 1] - q)2 In other words, there exists
Proof. Suppose f(r;; X*) is not marginally quantile consistent
some A + 0 such that
Pr [s S f(x) + Alg((x) = 1] = q- (m.a)s
15

---

Under review as a conference paper at ICLR 2023
Suppose we patch ((:Aa)
f' Patch(((;
which can be re-written as
f((x) f(z; X²) + 1(0((x) -
= [(xx + Σ Xg g(x))
+ A -11((()))
= f(x) + Σ X₂ g(x)
gEG
where + A and X/ Xy for all other + g'.
Lemma 3.2 yields
PB (
<0
which contradicts the fact that X is an optimal solution to min, B(zyyDD Lo (f():
B.3 MISSING DETAILS FROM SECTION 3.3
Claim 3.1. f f a-approximately quantile multicalibrated with respect and q, then
Va
1, Pr y -. (2.g)/D
for g E G, v E R(f).
/ (
Proof. Consider any E G.
Pr [f(x)= = =11(9- (1,s) (
Pr (s) =11 11) 2
Q(f.g)
Σ
(0.8) (
vER(S)
(g(
In particular, since each term in the sum is non-negative, we must have for every R(f):
Pr [f(x) vlg(x)) = 1] (o Pr [s f())ff()) v. 9(x) = =1) (0,0)~
(w.s)~
Sloc)))= 1]
Dividing both sides by Pr(a.e) vlg(x) 1] we see that this equivalent to:
2
q -r-uepp S f(x))f(x) = (1]()) = = 11) 5 Pr(a.s)~s (g(x) = 1, (T(x) vl
a
Taking the square root yields our claim.
Theorem 3.2. Suppose S is p-Lipschitz and continuous, and m 8p" rounds, Algorithm BatchMVP(J. 9.9.9....p. S. m)) returns fr such that
After S
32p o²
many
PBS (JT) S PB, - 32p -
2. fr is a-approximately quantile multicalibrated with respect to G and q. In particular. via Claim 3.1, we have for every and u E R(f),
Va
Pr [ TT = 1.)x(() - 9 /Pr())))S(g()) 1r (x.W)D
Proof.
16

---

Under review as a conference paper at ICLR 2023
(1) Marginal quantile consistency error in each round t: At any round t, if fe is not approximately quantile multicalibrated with respect to G and q, we have
Pr x E B,] (9 q- (a.s)~S
2 fa(a)aa B.i)
Pr [s S (2.a)~5
m 1
2m
as the average of m elements is greater than
(2) Decomposing the patch operation into two patch operations:
Write
A argmin Pr [s S fa(a)) + A|E E B,) - (2,8)~5
Ae[0,]]
to denote how much we would have patched Le by if we actually optimized over the unit interval. Then, divide the patch operation into two where
f-11= Patch (fe, B₁, A1)
fi+1 Patch (fi, B,, Bi, A. - -
Now, we try to bound the change in the pinball loss separately:
PBC()) -PB (f.) (PB) (f+1) PBG (f+r1) (LI) PPB (00)
(4)
(2) Bounding (**): Lemma 3.2 yields
(**) = PBS (fe+1) - PBS S 4pm
(3) Bounding (*): Note that i < Â
++ for some i E [O..... m 1]. Because the function is increasing function in A, have
A Pr(m.)))SBB, (s f((
Pr is S f(()) + A1 <
Pr (
$ $ f((x)
for any A <
(B.
m
i+1
Pr S [t(x) + A (I,s)~SBB
Pr (k,s))~SBB Bg
8 8 f((x)
for any A
m
m
Because S|B is p-Lipschitz and for (x) is q-quantile for Br, we can bound the marginal quantile consistency error of fr+1 against S)B as
In other words, A E { ++1 so we have A
A < m
m
Pr SI,
[s S f(+1(x)) - -9
Pr is fe+1(=)) (2,0)~SBB
Pr (I,0)~SIB
f(< A + Ad S m
as A.
Årl < 1
Note that fe+1(1) Te+1(2) for x & B and [++1(x) = fe41()) + + ~, for x B, where
JA, - Â. 5 L. Applying Lemma 3.1 with A D. Â., a S L. and (f.f") = (fr+1, fo41). we
have that
- PB, (f+r1)
Pr (x B.) (PBSIB. (Set1) PBSIB. (J+1)) (2.5)-
(p1
P 2
$ Pr (o BB].
(2,8)~
m m
m 2p
P
m?
17

---

Under review as a conference paper at ICLR 2023
(4) Combining (*) and (**); We get
(f(+1) (
P m²
4pm
a²
32p
(5) Guarantees: It directly follows that
a²
BB (ST) PB (fo) S p2p
With 0 S (R)()) S for any : X - [0, 1]. we note that fr must be a-approximately quantile multicalibrated with respect to 9 and after at most 32g" a many rounds.
C MISSING DETAILS FROM SECTION 4
C.I ON THE LLI.D VERSUS EXCHANGEABILITY ASSUMPTION
Remark C.1. In this section, we prove PAC-like generalization theorems for our algorithms under the assumption that the data is drawn i..dd from some underlying distribution. Exchangeability is a weaker condition than independence, and requires only that the probability of observing any se- quence of data is permutation invariant. De Finetti's ss representation theorem (Ressel, 1985) states that any infinite exchangeable sequence of data can be represented as a mixture of constituent dis- tributions, each of which is i.i.d. Thus, our generalization theorems carry over from the i.i.d. setling to the more general exchungeable data setting: we can simply apply our theorems to each (i.i..)) mixture component in the De Finetti representation of the exchangeable distribution. If for every mixture component, the model we learn has low quantile multicalibration ervor with probability 1 - 8 when the data is drawn from that component, then models with also have low quantile multicalibration error with probability 1 1 in expectation over the choice of the mixture component.
C.2 HELPFUL CONCENTRATION BOUNDS
Theorem C.1 (Additive Chernoff Bound). Let (X2) ) be independent random variables bounded == such that for each i E [n], X, E [0, 1]. Let Sn, = > X, denote their sum. Then for all >> 0,
Pr S, E[Sa]| 2 c 2xxp (X
n
Theorem C.2 (Multiplicative Chernoff Bound). Let {X be independent random variables bounded such that for each i [n]. X; E [0, 1]. Let Sn Ei= X, denote their sum. Then for all
> O,
EE(Sn]n
Pr SS - R[Sa]l 2 [| & 2 exp (X.
3
Lemma C.1. Fix any B C X. Given { 3:) bi) ~ S", we huve
n
3ln 2) Prs(x B
1 I E BJ - Pr (2,8)
x
E B <
Proof. This is just a direct application of Chernoff bound (Theorem C.2) where we set 3lm
PPs [
Lemma C.2. Fix any B S X and [0, 1]. Given S [121, st) ~ S", we have
31n P f(x), B)
3 31n ( Prs(æ e B]
n Σ 1|s < f(x), B
Pr (2.6)
is < f(x), E B
n
18

---

Under review as a conference paper at ICLR 2023
Proof.
This is just direct application of the Chernoff bound (Theorem C.2) where we 3lm(3) a /
Lemma C.3. Fix any B _ X and f X - [0, 11. Suppose have that with probability 1 -
1nn Pr
S 2'
Given S D", we
Pr (1,0))-1B
1s S [xx)]
Pr (a,8))-8B
[s S f(x)]
Prs x B
Proof. Note that
- 18, S (24), E B)
Pr [s f(x)] (#,5)~518
1/ - 1 [ E B)
Lemma C.1 and C.2 together give us that with probability 1 - 8,
3 In ) Prs(s S f(x), B) 1
3 ( Prs (a E
1 [ss & f(xi), E B
Pr (2,0)
[s I f(x), B
n
n
1
3 3 ()) Prs(æ E B
1 J. E B]
Pr (1,s)
[or
E B)
n 1=1
3lm Prs()
With
we can show that
n
Pr
ss S fx)]
(2)8)~-8BB
1 E 1[s S fx;)), x2 E B
E [[x; E B]
< Prs(a S f(x), x E B) +
Prs(# E B] -
Prs|s S f(x), B] +e
Prs(# E B)
ProfrcB
2x
Prs(s S f(r) E B +
B)+C)
1 Prs(ø B)
Prs(æ E B)
(+)
2e
2ca
$ Pr S {[x)]] + Prs(0 E B)
+ Prs E B
+
S|B
Prs(z E BJ²
3ln(1)
3ln(2)
< Pr(s <1(x)) +33 +3V n nPss x B] S|B
+2 n
Prs( B
(ln(4)
Pris < [()]] 55 n Prs(x E B SB
)luig)
where for (*), we rely on the assumption that V PP[aeB
S 2 apply the inequality 1/(1 x)) S
(1+2x) for < x S 1/2 and for (**), we we on Pra
3lm $)
S 1 get Pro(keB
3lm(2)
3lm(1 () n Prs Pas
Lemma C.4. Fix any B X and f X [0, 1). Suppose have that with probability -
3 Pr([EBB]
I 2.
Gäven S ~ D=,
(9 9-
3l #
Pr is S f(x)] (2,8)~SBB
-(1- q-
Pr (r,))
[s S f(())]
$ $20
n Prs E B
19

---

Under review as a conference paper at ICLR 2023
for any q E [0.
Proof.
99- -11-
q
Pr
Is f((wa)]
Pr Is S f((001)
(0,0)~811
(2,0))S11
29
[s I f(x)]
Pr - f()))
+ Pris S f(x)]] - Pr(s - f(2)1²
S|B
SIB
S|B
$1B
Pr S f(x)] - Pris - f(x)1
Pris S f(x)] + Prls - f(w0))
2
Pr [s S f(x)]
Pris f(x)]
+
Pris
S
$|B
BB
8|B
$|B
S|B
< 4
(s S f(x)]
Pris < [(x)
S|B
$|
3 In(
s 200
n Prgg[ E BJ
where we use Lemma C.3 for the last inequality.
Lemma C.5. Fix B C N. E 1th E G. and f X + [0, 1]. Given S ~ D", we have with probability 8
Pr to ( B1] (a- Pr (a.s)
1o E Bi (0- Pr Is f(x)) (2,0)~SSBB
Pr (a,0)~s
[s S f(x))
(1,,))
31n( Prs(e B)
12
$ 1
n
n
3ln(2) no P
Proof. First, Suppose
2.
Then, with probability 1- 8,
Pr
[B]
9
Pr
ss I f(x)] [s(((>]]
(x,s)
(0,6)/& B
3 3 2) Prs(æ E B]
Pr
B +
(a- (1,
(1-
Pr
(s S [(x))
Lemma C.I
(2,5)
3 31n () Pro(z e B]
<
Pr
B +
q
Pr
is f(x)]
<
(2,5)
(2,8)~$1B
12 In
3 31m S Prstr E B
3 In (
Prs B
2
On the other hand, we have
12 ln
Pr [B] 9- Pr [s S s(x)) (5
s Pr [B] <
(1
n
Because |a- bl S max(a, b) for a, b E 1). we have
2 Pr is S f(x)]] (1.,))
Pr [B] (9 (9- (x,e)ni
Pr Is S f(x))) (x
Pr
[B]
(9-
(
20

---

Under review as a conference paper at ICLR 2023
3 1n( (3) Prs(æ E B
12 In )
Th
m
3ln(3) PPr B5
Now, suppose otherwise:
3. Then, Lemma C.1 and C.4 promise us that with proba-
bility 1-6 8,
2
Pr [B] a- (2,5)~
Pr
I s(x)]
(1,8)~8811
(1-
Pr
[B] ((1)
Pr
1s5 (.SS(x) (((5))
+
(ar,))ms
(1.8)~
Pr
B
q
Pr
[s S f(xx)
+ Pr (1,,))
Ble2 +
(
(x,8))~BBB
31m ) Pre(sen
3lm(3) nPrs [
where 61
and
62
20
n
We can show that
Pr (x,3)~
Blez + 61 6
31n( Prs(æ B)
3l
< 21
The opposite direction works the same way.
C.3 OUT OF SAMPLE GUARANTEES FOR BATCHGCP
Theorem C.3. Suppose S is p-Lipschitz, and write f(xx²) = BatchGCP(f. 9. D) and
f(x)p)) = BatchGCP(f G, 9, D) given some D = {(Ii, y1) y)}r drawn from D. Then we have with probability 6 over the randomness of drawing D from
Pr ly E (T(AAb))())ll( = 1)]-999 9 S Pr(g(x) 1] (a.y)~
a'
where ((())))
{y s(z, v) S fz: {b)} o' max(q, 9). b b [maxx 11
In( 244 + (9] (n(1+2n)
and a' = 24pby' V
Proof. Fix some B E N. For any fixed where ||a||2 S B, the Chernoff Bound (Theorem C.I) with rescaling gives us that with probability 1 - 5 over the randomness of drawing D = { Y from D.
n
In
(f(f())))))))
(=; A), S 4g $4''By
BV
(x.D)~
2n
as A + (f(((z,)) A). y) q' -ippschii
We now show how to union bound the above concentration over all À where |||||2 B. To do so, we first create a finite e-net for ball of radius and union-bount over each the net. Then we argue that due to the Lipschitzness of the pinball loss Iy. the empirical pinball loss with respect to each that is in the ball must be concentrated around its distributional loss.
We fist provide the standard e-net argument:
Lemma C.6. Fix E R and B E N. There exists a Ry = -fi...., A where kB S (1 +1+ 2B 191
such that the following holds true: for every where || I B, there exists j E [k]] such that ||> X <.
21

---

Under review as a conference paper at ICLR 2023
Proof. For simplicity, write PB {A E R! ||il|2 B).
We say that set R S IR is an c-net of PB if for every À PB, there exists X E R such that ||A- 2 e.
Without loss of generality, suppose B 1. Since an B B-cover of Pi can be scaled up to an e-cover of PB- i.e. given R2 which is an f cover P1, the following set Rg = (B-A: À R1}
an e-cover of PB.
Now, choose a set R to be a maximally e-separated subset of P1: for every u, u E B, ||u - u 2 and set Rt such that R R! has this property.
Due to its maximal property, R must be an e-cover for Pt. Otherwise, means that there exists some point E P1 such that for every E R ||u e|| > Note that R U {u} would still be an e-separate subset Pl, contradicting the maximality of R.
Due to the e-separability of R. have that the balls centered each u E R with radius of ă is all disjoint, meaning the sum of the volume of these balls is the volume of their union. On the other hand, we have that they all lie in ball of radius 2. Pi+s- Therefore, have
PP](P;) | S (P
Since vol(P.) = cls). (P)), we have that
[ 1 (1 + 911
1 2 16
9
By union-bounding inequality (1) over Ro, we have that with probability 1-
In 1n(2
max jE(kn]
Lf(((r)))))))
I < 4g/B1 BV
(2.0)~-
2n
Using e'=Lipschiszness of Tug. we can further show that for any À where |||||2 S B, we have
1 (y(f(;;)))) A) - E (z: A),
(a.9))
Tn(f((n))) N).0)) 1
(f(((
E
LL (f(;;; (x):)))))1
L (f Ag),
E
(L 2),
(x
(w.y)~/D
(x.0)D
(1): -
[L ( (s; {5),
(x.y)~D
L (f(:;; (z: Az), vDDI
E (a.v)~D
(L
(a.y)~D
In(?) + In(k
< 2eg' + 4g' BV
2n
In(2) + 9 In(1 +
27
-2og' 4g B
2n
22

---

Under review as a conference paper at ICLR 2023
where j is chosen such that || Xا1l2 and find such j because Rg is an c-net for the ball radius B.
Setting yields
2Bq + 4e/ BV
In(3)= + 9 In(1 2n) S 6BB'
In(3) + | [g] + 2m)
2n
2n
for sufficiently large n.
We set 65 ously over all b E N and where ||al2 Sb
66 т.6 so that 2 On = 6. In other words, with probability - 6, we have simultane-
In(
7262 35 )
|9] In(1 + 2m)
L.(((=8))..))
L (I v). s Gbd') (0.))-
2n
In other words, the final output Xb from BatchGCP and X which is the optimal solution with respect the true distribution D must be such that
In(
2262
+
9 In + 2n)
E (x.D)e
I 6bby))
36
2n
In( mab2
+ [g + 2m)
Lg (f 2²),)))
E
(f; (1;
S 6bg'
36
(2.0)~D
2n
where b = mmax (1 || 122 [|Abl12)] In other words.
In ?2
In(1 1 2n)
E (=:)>>
[Lg (f Ab)
E (f,((((;;;)) 12hv V
(2,9)~D
2n
Now, for the sake of contradiction, suppose that there exists some E 9 such that 2
[g(2)= 1] 1]] (1 P |s S f(1; (b))((<) = =1] > a' (2,6)~08
Pr
(ar,))
In( R82 )+10) In(1 (n1+22n))
where 24pby'
2n
Then, Lemma 3.2 tells that can decrease the true pinball loss with respect to Xb by least 2p by patching B {ar g(x) = 1). However, that cannot be the case that as that would mean there exists X' such that
(=; (=,8)~
E (Ly(f(;;>))
(x,0)~
(
where X' is such that Xg X for all g * g and Xg is chosen satisfy
== Pr (x + Xgl9(x) 1).
(a.g)~
This is contradiction as we have already defined
X = arg min
E [4 (f(1; (x.n)~
C.4 OUT SAMPLE GUARANTEES FOR BATCHMVP
C.4.1 OUT-OF-SAMPLE QUANTILE MULTICALIIRATIIC BOUND FOR FIXED T
Theorem 4.1. Suppose S is p-Lipschitz and S S". Suppose BatchMVP(f, 9,, 9, S, m) (Algorithm 2) runs for T rounds and outputs model ST. Then Jr is a' -approximately q-quantile mulicalibrated with respect G on S with probability
where
3p² (In(
472T2 36
+ TInn
p'(g a²
12p²
4t 22p
+ T
In
o' = a
36
0²
2an
an
23

---

Under review as a conference paper at ICLR 2023
Proof. For each E N, define 5, = 6.
6 n² (2.
Note that
6 π
as Σi=1 8.
Fixed any & N and d. Union-bounding Lemma C.5 over E 9 and f E C., we have that for any g E G, with probability 5-
- ( = =.)((=== = =1] (1)0)))111100 Pr [(()) = 2
Pr (2,5) .EN(S))
Σ
(x,3))
-1(11-
2
Pr
[f(()) = ((r) =1] 9-
Pr |s -0 0,g(z) = =11
=
BEA( (2,4)m08
3 (In(x)) + =nnn44m 9)) Prs P =1 12( () +t + In (gD))
Σ 2
vER(S))
We can further bound
(x)
3 (In( + In(4m2](1) Prs(f((z)= = v,g(x) = 1] + 2m 12(ln(}) + t 11nn4mmm (G))
(x) 5 Σ
1
n
n
vER(())
3 (In()) + +1mmm2 G))
Pes Prs|o(=]=1]
4m g)) |R())*+ + 12p²(In( + t In 111m4mmm
R(,+)]
S a + 2
am
(+))
(In(}) )= t (1((4m]())) [R((+))
12p² (In(5) + In In(4m=
s 211
n
an
3p² (In(*) + t 1n GI)
12p" (In(}) () + + 4m 4m
211
4am
an
3p2 [In()) + t tnn In(
12p² (In
) + In e 9
2an
an
where we used [R(f)) = m +1 < 2m and m 2.
Inequality (**) follows from the fact that
M(2) 31 (n(( is concave and so the optimization problem E! h(zz) where
DIR(NN 2, = Prs(e(x) = 1) is maximized at 2; Pra(g(e)=1) for each i E [[((f]].
[R(J]
In other words, with probability 1-6 ô = 1 Ei 8., we simultancously have for every E N
2
Σ Pr (f(o)) = v.g(2) =1] (1 (2,5)
Pr I (
vER(S))
Pr 11(0)) =v =
=1] q
= v, Pr [s S -,)((())((()))_(()0)))))))))))))
vER(A) (2:8)
(m,s)~u
3p2 [nn ( + +nnn وو
12p² (In ) + In ااااا
+ 21
2am
am
24

---

Under review as a conference paper at ICLR 2023
2
Σ
Pr = 22 =1] 9-
=1](9-
Pr
|s S f((x))ff(x)) v.g(z) =1]
vER(S.) (2,0))
(2.0)
3p²
[n(
4x 36
) + t In
10'
a²
12p²
1= 36
+ In (1
+ 21
+
a²
2an
Finally, when our algorithm halts at round T, fr is a-approximately multicalibrated with respect to its empirical distribution S. Therefore, we have
2
Σ Pr (1,0)~5 (T)) = =11 -
Pr (a,s))us
DE (ER((T)
3p²
In 1x222) + In p((
12p²
4x" 36
+ In( p910) ))
20n
an
C.4.2 SAMPLE COMPLEXITY OF MAINTAINING CONVERGENCE SPEED OF BATCHMVP
We write Co {So) and
[x)1())= Patchh(f: B(u,g), A) where B(v,g) = (a f((x) = v, ())(()==
C++1= f(11 1}
for all ft C,,UE g = G. [+]].
to denote the set of all possible models what dataset S {(x1, st)) is used as input.
could obtain at round t of Algorithm 2 regardless of
Lemma C.7. Fixing the initial model fo. the number of distinct models ft that can arise at round t of Algorithm (quantified over all possible input datasets S) is upper bounded by:
|Crl ((m + 1))1g1)* < (4m²lg))*.
Proof. The proof is by induction on t E N. By construction we have |Col = 1. Now, note that |C++1| = (m+1) because we consider all possible combinations of f. E C, v E m 1 E
G, and A Therefore, if [C,| = ((m + 1) for some I,, then |C++1l = ((m 1) (1) n
Theorem 4.2. Suppose S p-Lipschitz and continuous, S ~ S consists of n iid. samples drawn from S, where n is sufficiently large: n Z
2a and our calibration set
92928 (In
1280
+ 8pa In [210)) max lat a.) Then BatchMVP(f,, a, 9.9....p.. S).m) (Al-
a
a
a=
gorithm 2) halts after T
rounds with prob. 1 8.
Proof. Fix any round Because fi is not a-approximately quantile multicalibrated with respect to and g on S, we have
Pr ( E Bi] g- Pr Is S fe(x))x E B.l) (
a
> +
(2,s)~5
2m
Now, the patch operation in this can be decomposed into the following:
Ut + Ut + A
where g (B.S)~S|BB
Pr [s S f((x) + +
1 + A + + A
where A-= arg min
|V - A vE[l/m]
22 + Å + A
25

---

Under review as a conference paper at ICLR 2023
For convenience, we write
f7 f((2) + 1|r E B:]
f1(z) - f((z) + Á 1|r E Bi]
f+1(#)) f((x) A. 1 B:]
Now, we show that we decrease the empirical pinball loss PB$ as we go from fo to fi+1 in each round with high probability.
(1 J7: First, we can show progress in terms of the pinball loss S and then by Chernoff bound, can show that we have made significant progress on S with high probability. More specifically, we must have decreased the pinball loss with respect to B by going from it to 2t A" Note that A is chosen satisfy the target quantile q with respect to S and S is g-Lipschitz.
Because the empirical quantile error was significant for (ve, we can show that the true quan- tile error must have been significant. By union bounding Lemma C.5 over all f E C, and using Lemma C.7 bound the cardinality of C.. we have with probability 8
Pr [Bi] (1- (9- (1,0))us
Pr (B.s))~SBB
[s S (sS((x)))
Pr [Bd]] 9- (0,
Pr Is S f((wa) (a.a)~~)BB.
31n( (CC Prs|# E B) 12 &Cd
< 211
(In(g) +ln(4m2(9)) Pro(æ E BJ
12 (In(g) 1n(4m2 91)
s 1
n
12 (In(*) + #n 9))
$ /
n
as long n 2 (In(}) + (n)) In other words, we have
Pr [Bi] (q
12 (In
8
+ 11(44m?
Pr
f((z))
221
(w,S)~
(B
2m
n
92928m 02928m²((n(3 (In(3 {) )+ In(4m² 91)
n 2
then we have
a²
Pr
[Bo] q
Pr (I,8)~S|B
[s f((((())
(x,8)~8
4m
As ft achieves the target quantile against S)B and the quantile error was at least i applying Lemma 3.2 yields
8mp
(2) fr -:: Recall that À results from rounding A to the nearest grid point in [-]. Because B is P-Liscchitz and fe(.) + A satisfies the target quantile g for S) Be, we can bound the marginal quantile consistency error of f((-) + A against S B, as
Pr [s S f((z) + A- 9
Pr Is S f((x) + +
Pr [sS f(()) A+]
<
(z.5)~SBBB
(r.8)~S) B.
(2.0)~SBB.
2m
A
26

---

Under review as a conference paper at ICLR 2023
Note that (x) ft for & B, and (x) f44( + -Á-- A") for E B, where
A A 2m Applying Lemma 3.1 with A Á A", 2m and (f, (st: fi).
have that
PB (ft) (J²)
Pr for BB.] (5.s)~
PBS|B: (ft) PB PBSIB.
p 1
)
p
Pr lor Bi]
(2,8)~0
2m 2m
2mn
2p/
P
8rn2
We have so far shown that with probability 1-
PB (f+1) - (fi)
PB (s+1) - (JB(()t) + ()t) + (PBB(1))) - (P)((())
< PB (()))
- -PB
P
a
+
8m2
8mp
By union boudning the Chernoff bound (Theorem C.I) over C++1, we can show that SB (ʃ) con-
centrates around PB (f) for every f E C. with probabiliy 1 ó, we simultancously have
In + t ln(4422lg))
PB (f) (B)(F)) 1
2n
!n( + 1n(4421l))
(f:)) PBS PBS((P)) s
2n
In ( + 1n(4m2|9)
PBS (f(t1) PBS (fetz) $
2n
St, Ji, se+1 E C.+1.
In other words, we have with probability - 20
(f PB
In(3) (1n(4m2(9))
$ (PBS(J+42) - PBS
- (ft)) + P a
(f++2)
+ +
8m2
4mp
2n
(3) fr ft41: Because A, is chosen to minimize with respect to the empirical distribution out of grid points [1/m], we can show that the pinball loss against the empirical distribution Š must be lower for fe+1 than fü-
We can calculate the derivative of the pinball loss with respect to the patch A as
d SIB (((()+1) dA
d (1 S| [Te (x(( + 8)
dA
1
Σ
(,(f(xx)) + 5;)
B,
dA
i: EB.
Σ
dA (f((x)))) + +1,s)
Σ
dA (f((zz)))+ +1,
[
27

---

8p" Under review as a conference paper at ICLR 2023
1
Σ (1-9)-
Σ
im Ea Si 9)
[
[i :f: E Bi,8; S f((())) -31--
[B.]
Pr [s S f((x) + A] - 4-
(z,s),&BBB
Because PBS|B, (f(())+A) is convex in A, minimizing this function is equivalent to minimizing the absolute value of its derivative, which is how A, is set. Therefore, PB (f+(++++ +)) is minimized at A. Hence, we have with probability 18 (Ō to argue that there is significant quantile consistency error B, with respect S and argue that the empirical pinall loss concentrates around its expectation),
(n( + t (4m² (g))
< S (f(+1) -PB (ft)) PBB((f))
P
+ -1
8m2
8mp
2n
41/ In(3) + + +In44=])G))
8m2 Smp
2n
-a
In( + +t (
S
+
+41
4p
2n
0²
as we have chosen m
2n
If n 2 312p"(In In(mm² 1911)
we have
a²
PB3(S))
8p3
Because we decrease the empirical pinball loss by 85 in each round with probability 28, we have that with probability 1 - 1- a2
8p"
the algorithm halts at round T = a2
If
8
8p3 In(4m)
m2 p
2 92928 In
9)) max
a
a a4
we satisfy all the requirements that we stated previous for in each round / E [T].
we set 8' a we have with probability 8', the algorithm halts T require
80a
where we
128p2 a²8
8p3 1n(4m?|g)) a²
m p
2
92928 In
max
a
a4
128p²
8p"
( max
p² p
92928
In
In
a²8
a a
4 a
D ADDITIONAL EXPERIMENTS AND DISCUSSION
D. A DIRECT TEST OF GROUP CONDITIONAL QUANTILE CONSISTENCY AND QUANTILE MUL.TICALIBRATIO
In this section we abstract away the non-conformity score, and directly perform a direct evalua- tion of the ability of BatchGCP and RatchMVP to offer group conditional and multivalid quantile
28

---

Under review as a conference paper at ICLR 2023
VELE MIN CoNrE CIusoss
Figure 6: Per-group coverage of Bat (left) and Bat chGCP (right) on a representative run.
Group-wise Quantile Calibration: BatchMVP BatchGCP
0.00115
Ingou QuANEN Caltration Eree
tatchGCP
0.03500
0.00100
0.00055
0.99055
15
Group Number
Figure 7: Per-group calibration error of BatchMVP and Bat chGC on a representative run.
consistency guarantees. We produce synthetic regression dataset defined to have set of inter- secting groups that are all relevant to label uncertainty. Specifically, the data {(2,, y:) } 10000 E (Z, x R)10000 is generated follows. First, define our group collection as G= {91,-... 915).
where for each j = 1, I,.... 15, the group Jj = {j. 2j, 3j. C Z.4 contains all multiples of j. Note that group 91 encompasses the entire covariate space, ensuring that methods will explicitly enforce marginal coverage in addition to group-wise coverage. Each 2; is a random integer sampled
uniformly from the range [1, 5000). We let the corresponding label y/4 | I E [o, 1], where y is distributed as the sum of n2(;;) i.i.d 1) random variables, where n² is the number of groups that v; belongs to. After generating our data, we split it into 80% training data Dtrain and 20% test data Drest. We then run both methods the group collection G. for target coverage 0.9, with m 100 buckets.
The group coverage obtained by both methods on sample run can be seen in Figure 6. Generally, both methods achieve target group-wise coverage level on all groups, with Bat exhibiting less variance in the attained coverage levels across different runs Meanwhile, the group-wise quan- tile calibration eтrors of both models are presented Figure 7. Both BatchMvs and BatchGCP very well-calibrated on all groups, with calibration errors the order of 10-3 unlike BaMChMVP, the definition of BhGC does not enforce this constraint explicitly.
though
D.2 FURTHER COMPARISONS ON STATE CENSUS DATA
In Section 5.2 we performed an income- predictto task using census data (Ding et al. (2021)) from the state of California to compare the performance of BatchGGP and BatchMVP against each other, as well against other regularly used conformal prediction methods. Here, we present results of the same experiment using data from other US states. We selected the ten largest states (by population data) to work with, of which California is one. Results for every state averaged over 50 runs of the experiment, taking different random splits over the data (to form training, calibration, and test sets) each time. The plots in Figure 8, Figure 9, Figure 10 and Figure 11 compare the performance of all four methods with metrics such as group-wiss wise coverage, prediction size, and grse quantile calibration enror.
29

---

Under review as a conference paper at ICLR 2023
(a) Texas
(b) New York
(c) Florida
Pennsylvania
(e) Illinois
(f) Ohio
(g) North Carolina
(h) Georgia
(i) Michigan
Figure 8: Results for group-wise coverage for nine different states (averaged 50 runs) using different methods of conformal prediction. Error bars show standard deviation.
D.2.1 HALTING TIME
Recall that our generalization theorem for BatchMVP is terms of the number iterations T runs for before halting. We prove worst-case upper bound on T, but note that empirically BatchMVP halts much sooner (and so enjoys improved theoretical generalization properties). Here report the average number of iterations T' that BatchMVP runs for before halting each state, averaged over the 50 runs, together with the empirical standard deviation.
Texas: 10.84 = 1.2059.
New York: 11.26 + 1.2134
Florida: 12.06 + 1.4752
Pennsylvania: 11.68 + 2.3189
Illinois: 9.74 + 1.4941
Ohio: 10.94 + 1.7482
North Carolina: 13.22 = 1.5138
Georgia: 12.18 + 1.6454
Michigan: 11.24 + 2.0353
30

---

Under review as a conference paper at ICLR 2023
(a) Texas
(b) New York
(c) Florida
(d) Pennsylvania
(e) Illinois
(f) Ohio
(g) North Carolina
(h) Georgia
(i) Michigan
Figure 9: Results for group-wis average prediction set size for nine different states (averaged over 50 runs) using different methods of conformal prediction. Error bars show standard deviation.
31

---

Under review as a conference paper at ICLR 2023
(a) Texas
(b) New York
(c) Florida
(d) Pennsylvania
(e) Illinois
(f) Ohio
(g) North Carolina
(h) Georgia
(i) Michigan
Figure 10: Results for group-wise calibration error (averaged over 50 runs). Error bars show stan- dard deviation.
32

---

Under review as a conference paper at ICLR 2023
(a) Texas
(b) New York
(c) Florida
(d) Pennsylvania
(e) Illinois
(f) Ohio
(g) North Carolina
Georgia
(i) Michigan
Figure 11: Scatterplots of the number of points associated with each threshold- group pair (g, Ti) against the average coverage conditional on that pair for all g E and all т; in grid, over all tested conformal prediction methods (consolidating results over all 50 runs), for all nine states. Target coverage is = 0.9.
33


Reviews:
[{"review_id": "cKVLfFBvoIf", "reviewer": "Reviewer_3CEp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper extends the scope of conformal prediction techniques from marginal validity to conditional validity with respect to a subset of the feature space. This allows for example to quantify the uncertainty of predictions conditional on the race or gender of the subpopulations. The main novelty lies in the fact that instead of thresholding the score functions by a constant to satisfy the prescribed coverage, the authors propose to learn a threshold function under coverage validity constraints. This is very similar to what is done in learning under fairness constraints. The authors present a series of numerical experiments illustrating the performance of their method, a clear improvement over the alternative method.", "summary_of_the_review": "Some comments/questions:\n\n1) By construction, Conformal Prediction is distribution free. The propositions of this paper are not, since they significantly restrict the CDF with some regularity assumptions, that in-fine, cannot be verified because the distribution of the data is unknown. Can the authors comments on that?\n\n2) A core assumption, all around the paper, is that the scores functions are $\\rho$-Lipschitz. However, the latter depends on the distribution, which is also unknown, Even more, the scores are constructed from the data eg as prediction errors of a neural net. How do one verify this assumption? More annoying, the proposed algorithms do not even use the regularity constants in play, which suggests, with a bitter taste, that the theoretical analysis is not connected to the proposed algorithm. The authors might want to discuss this a bit more.\n\n3) Considering the context of the article, the exchangeability assumption is perhaps a bit too strong. It would be surprising if the population of the considered subgroups follow the same distribution nonetheless being independent. When considering age or gender, can the authors present any example where such assumption is realistic?\n\n4) When conditioning on an under-represented group (ie where very low number or none of examples is observed), the conditional event becomes a rare event. How does it affect the length of the conformal set proposed?", "strength_and_weaknesses": "The idea of learning a threshold function is very innovative and can certainly be applied in other contexts. The numerical demonstration is very convincing and the subject in general is relevant for the AI/ML community.\n\nThe major weakness of the paper is that it is very hard to read. The proof does not seem to be written to be read at all. Same expressions are repeated several times, making it very messy, and very difficult to understand. The authors would benefit from reducing this clutter in the proofs. An example is the proof of Lemma C4, where the core tool is just the application of classical remarkable identities to bound $|(q - a)^2 - (q - b)^2 |$. \n\nAlso, it is very difficult to understand under which hypotheses the proposed algorithms work, so much the article is convoluted with additional (sub)-constraints on the distributions. And this, from lemma to lemma, one gets lost and even after reading it multiple times, I have trouble extracting a clear setting where the algorithms are guaranteed to work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_SBJDDrKIqw", "reviewer": "Reviewer_auqC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a conformal prediction algorithm that obtains multivalid converge on exchangeable data in the batch setting. Multivalid coverge guarantees mean that the target coverage level holds conditionally on membership in each group or/and the threshold value. They provide theoretical analysis to clarify the reliability of the proposed algorithms under some regularity conditions. Extensive experiments have been conducted to compare the performance of the proposed method and other comparative methods.", "summary_of_the_review": "This paper proposes a novel method that has multivalid coverage guarantees. They theoretically analyse the properties of the proposed method.", "strength_and_weaknesses": "Strength:\n\nTheoretical analysis of the proposed method explains why it works.\n\nAdequate experiments are conducted.\n\nWeaknesses:\n\n-- The first sentence in the last paragraph on page 3, \"that on each input x output a value f(x) that is\", output should be outputs.\n\n--Please provide some examples that satisfy the Lipschitz condition in Definition 2.2.\n\n-- what is the meaning of this sentence \"To facilitate learning models f with guarantees conditional on their output values, ...\"?  Please give some examples of such f. Is m here the same as m in Algorithm 2? In general regression settings, finite cardinality seems unrealistic. In Section 5, please state clearly what f you have used, does it satisfy the finite cardinality condition? How do you choose m in practice (in Section 5, you use different m)?\n\n--From theoretical results, the sample size should be large enough for the results to hold (with high probability). For a comprehensive understanding of the sample size requirement, It will be helpful to provide more experimental results for different sample sizes (especially for small sample sizes).\n\n-- Is it possible to theoretically analyse the (average) size of predictive sets of the proposed algorithms (smaller compared to previous conformal methods)? Please provide some discussions.\n\n-- Please explain the parameters alpha, rho, m in Algorithm 2 and their connection. Are these parameters pre-specified by users or tuned in some way?\n\n-- The meaning of Figures 2 and 4 is not very clear. Please clarify this.\n\n-- From experimental results (e.g., Figures 1&3), the method, BatchMVP, might obtain predictive sets that undercover in some groups. Can you explain this?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OIzXuqVIa9v", "reviewer": "Reviewer_FUsZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies distribution-free multi-valid coverage in the batch setting. They provide two algorithms to achieve multi-valid coverage, which is a stronger notion than regular marginal coverage. In a brief summary, they design their algorithm based on a theoretical argument that patch operation such that a postprocessing and make sure coverage guarantee when conditional on x\\in B  for a set B can decrease pin-ball loss, which is the a key loss for quantile control.", "summary_of_the_review": "See commentes above.", "strength_and_weaknesses": "Strength. This paper is technically sound. Conditional on group membership has important application.\n\nWeakness. I am a bit confused about the writing. I am generally familiar with a conformal prediction on the statistics side, but this paper is a bit hard for me to parse. I think it mainly follows a line of literature in CS, which I am not familiar with, and a terminology explanation is missing. For instance, I cannot understand what is the difference between the batch setting in this paper and the setting studied in standard literature, though the paper clearly says ``it is different from the sequential setting because the labels are not applicable when the set is deployed\".  The algorithms are based on s, which involves y, does it mean they can only observe s and x? And the sequential setting I think it means online learning, but most of the standard conformal settings are just offline, what is the difference between those literature and batch settings? I also could not understand why a criterion needs to hold for all tau when conditional on f(x)=tau, this is a bit too strong. Also by replacing tau to f(x) is not novel, it is widely considered in the literature such as ``conformal quantile regression\" by Romano. Besides, the lipchitiz on distribution basically needs the density to be bounded, which is not applicable on many real examples in practice, such as applications in learn then test paper by Bates etc.\n\nSome minor comments, the set of distribution on \\mathcal X should use \\Delta_{\\mathcal X} instead of \\Delta \\mathcal X, which looks weird.\n\nI would raise my score if the author can provide more detailed explanation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "O2338-qair", "reviewer": "Reviewer_2Lnk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper looks at a novel way to investigate batch conditional coverage in the setting of conformal prediction. CP is known to be unable to provide conditional coverage guarantees and hence this paper proposed two methods to relax these assumptions but taking a closer look at batch conditional coverage and hence propose batchGCP and batchMVP.\n\nThe key insight is that their threshold contrary to CP is now a function of X which in turn is now to be learnt.\n\nBy adding this extra degree of freedom they are able to obtain interesting results regarding batch conditional coverage and show that their proposed method is superior compared to standard CP and other baselines.", "summary_of_the_review": "I have detailed all my concerns above and I am happy to increase my score if the above misunderstandings have been clarified.\n", "strength_and_weaknesses": "I will start with the strengths of this paper:\n- The authors propose a novel way to understand batch conditional coverage by utilizing the pinball loss in a specific way.\n- They also analyse the fact that the pinball loss might not always be well optimized and hence provide an iterative algorithm that sequentially improves the quantile computation.\n- They theoretically analyze the proposed algorithms and provide further theoretical analysis of how their method can achieve the guarantees (I am not familiar with the theory and hence I will be leave this part to be scrutinized by the other reviewers)\n- The experiments are mostly convincing and show that their proposed method is superior to current baselines\n\nIn terms of weaknesses and clarifications:\n- First of all I would like the authors to clarify what $f(x) = \\tau$ actually signifies. I am a little confused because wouldn't that mean f is a constant function? I just don't get the intuition on what the point of $\\tau$ is. Could the authors please give a concrete example of what tau signifies and why f(x) is constant? \n- In algorithm 1, I am confused to why you are computing the pinball loss wrt to y shouldn't it be the scores? maybe I am completely misunderstanding this part here but isn't f(x) supposed to be the quantiles for the scores? in that case, why are we minimizing the loss wrt to y the output? Sorry if I misunderstood sth.\n- I would suggest the authors to create a figure on how the patching works on a simple 1-2D example. I think that would illustrate the algorithm much easier. I get the general gist. My confusion also comes into algorithm 2. Isn't g(x) supposed to be fixed? i.e. these are the subgroups that we predefined. Now that we are optimizing over them how can we ensure that the groups that come out at the end reassemble the groups that we are interested in dealing with when all training is done? Also, what is the form of g?\n-  I am not familiar with PAC Bayes but a constant that big in 90k+ in theorem 4.2 seems not to be very useful. Even if it works in practice the theorem seems kind of useless. Please correct me if I am wrong here.\n- Could you please point me to the experiments where you increased the group size? I am confused to what breaks in your theory if each group is just an individual datapoint i.e. each group is just a 1-2 datapoint. Is there something that breaks in your theory or does that mean the bounds will become useless? I am just trying to get a more intuitive understanding on how the group size affects the overall bounds as in standard CP.\n- This is more like a clarification question: In the Barber et al 2020 paper do they do the following: split the calibration data for each subgroup and then compute a different threshold for each group. Then for testing time, they first check which group it is in and then sue the corresponding threshold for that new datapoint. If the answer is yes then please just reply with a yes, if no, please tell me why this is a  valid baseline if the calibration data is reasonably big for each group.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster