Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage
Authors: Konstantina Bairaktari
Jiayun Wu
Steven Wu
Venue: ICML 2025 poster (2025)
Keywords: conformal prediction
conditional coverage
prediction sets
uncertainty quantification
distribution shift
multigroup fairness
Primary area: social_aspects->fairness
TL;DR: We present Kandinsky conformal prediction, a framework that addresses the most general formulation of group-conditional coverage guarantees.

Abstract: Conformal prediction is a powerful distribution-free framework for constructing prediction sets with coverage guarantees. Classical methods, such as split conformal prediction, provide marginal coverage, ensuring that the prediction set contains the label of a random test point with a target probability. However, these guarantees may not hold uniformly across different subpopulations, leading to disparities in coverage. Prior work has explored coverage guarantees conditioned on events related to the covariates and label of the test point. 
We present Kandinsky conformal prediction, a framework that significantly expands the scope of conditional coverage guarantees. In contrast to Mondrian conformal prediction, which restricts its coverage guarantees to disjoint groups—reminiscent of the rigid, structured grids of Piet Mondrian’s art—our framework flexibly handles overlapping and fractional group memberships defined jointly on covariates and labels, reflecting the layered, intersecting forms in Wassily Kandinsky’s compositions. Our algorithm unifies and extends existing methods, encompassing covariate-based group conditional, class conditional, and Mondrian conformal prediction as special cases, while achieving a minimax-optimal high-probability conditional coverage bound.  Finally, we demonstrate the practicality of our approach through empirical evaluation on real-world datasets.

Kandinsky Conformal Prediction:
Beyond Class- and Covariate-Conddttinaal Coverage
Konstantina Bairaktari", ! Jiayun Wu 2
Zhiwei Steven Wu *
Abstract
1. Introduction
Conformal prediction is a powerful distribution- free framework for constructing prediction sets with coverage guarantees. Classical methods, such as split conformal prediction, provide marginal coverage, ensuring that the prediction set contains the label of a random test point with target probability. However, these guarantees may not hold uniformly across different subpopulations, leading disparities in coverage, Prior work has explored coverage guarantees conditioned on events related to the covariates and label of the test point. We present Kandinsky conformal prediction, a framework that significantly expands the scope of conditional coverage guarantees. In contrast to Mondrian conformal prediction, which restricts its coverage guarantees disjoint reminiscent of the rigid, structured grids of Piet Mondrian's art-our framework flexibly handles overlapping and fractional group memberships defined jointly on covariates and labels, reflecting the layered, intersecting forms in Wassily Kandinsky's compositions. Our algorithm unifies and extends existing methods, encompassing covariate-based group conditional, class conditional, and Mondrian conformal prediction as special cases, while achieving a minimax-optimal high-probability conditional coverage bound. Finally, we demonstrate the practicality of our approach through empirical evaluation on real-world datasets.
Conformal prediction (Vovk al., 2005; Lei Wasserman,
2014; Papadopoulos al., 2002b) is framework for constructing prediction sets with formal coverage guarantees. Given predictor f. X + y and n samples {(x,, Hi) from a distribution D, the goal is to build a prediction set function C that, for a given covariate vector Xa+1, outputs subset of Y guaranteed to include the true label with target probability. Ideally, the size of C(X.+1) reflects the uncertainty in f f(Xn+1).
A common coverage guarantee, termed as training conditional validity (Vovk, 2012), requires that for any f the training algorithm returns a (potentially randomized) prediction set function C such that, with probability 1 over the draws of the calibration dataset ((X, (,),, ke(x). the following holds:
(Ya+1 E E((x++1) {(X,, K))mm &
(1)
for some a and ō (0, 1). This guarantee ensures coverage on average over random test samples (Xn+1: Yn+1) drawn from D. weaker guarantee, called the marginal coverage guarantee, requires that P [Yn++ C((,+1)) where the probability is taken over all n + points (Vovk et al., 2005; Gibbs et al., 2023). However, limitation of such average coverage guarantees is that the prediction sets might undercover certain values of (X Yn+1) while overcovering others. A potential solution is to require (1-v))-overage conditioning on the value of (X,+1. Yn41). Unfortunately, we generally cannot obtain non-trivial prediction sets that satisfy such pointwise coverage (Vovk, 2012; Lei & Wasserman, 2014; Barber et al., 2021).
a,
However, various types of conditional coverage guarantees can still be achieved. For instance, Mondrian conformal prediction (Vovk et al., 2003) ensures the (1 coveraree guarantees over a disjoint set of subgroups defined over both the covariate Xn+1 and the label Yn+1. The method is named after Piet Mondrian, as its partitioning the space X' Y into a finite set of non-overlapping groups G mirrors Mondrian's 's iconic compositions of disjoint rectangles (see Figure 1). Class-conditional conformal prediction (for classification) (Löfström et al., 2015; Ding et al., 2023) can be viewed as a special case of Mondrian conformal
Equual contribution Khourr College of Computer Sciences, Northeastern University, Boston, MA, USA. "Shool of Computer Science, Carnegie Mellon University, Pittsburgh. PA. USA. Correspondence to: Konstantina Bairaktari <bairaktari.kk warrikke@otttteteeeddet.
Jiayun Wu <jiayunw andrew.cmu.edu.. Zhiwei Steven Wu <zstevenwu@cmmu.co
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditiona Coverage
H
Figure I: Composition with Red, Blue and Yellow, Piet Mondrian, 1930, Kunsthaus Zurich
Figure 2: Circles in Circle, Wassily Kandinsky, 1923, Philadelphia Museum of Art
prediction, where each label defines distinct group.
Similar to Gibbs al. (2023), our conditional guarantee can be leveraged to obtain valid coverage guarantees under distribution shift, provided that the density ratio between the test and calibration distributions is captured by one of the group functions we consider. While Gibbs et al. (2023) is limited to handling covariate shift- their group functions depend solely on X -ur approach extends to a broader class of distribution shifts affecting both X and Y.
Yet, the disjoint group assumption in Mondrian conformal prediction has notable limitations, as real-world subpopula- tions of interest often overlap. This is particularly relevant in algorithmic fairness, where protected subgroups-typically defined by combinations of demographic attributes such as race and genuer-naturally intersect (Kearns et al., 2018: Hébert-Johnson al., 2018). An alternative line of research addresses this challenge by developing conditional coverage guarantees for overlapping groups (Jung et al., 2023; Gibbs et al., 2023). However, both of their results restrict the group functions to depend solely on the covariate vector X,+1-
Our algorithm is computationally efficient, which relies on solving linear quantile regression over the vector space spanned by a set of group functions G. Similar to Jung et al. (2023), it preserves the key advantage of requiring only a single quantile regression model that can be applied to all test examples, rather than needing to solve separate regression for each instance in Gibbs et al. (2023). We show that our method achieves high-probabbility conditional coverage error rate of (( 112), where ng the number of samples per group on average, matching the minimax-optimal rate (Areces al., 2024). In the special case where group functions only depend the covariates, our bound significantly improves the O(n coverage error bound in Roth (2022); Jung al. (2023) in its dependence ng, and sharpens the dependence on [g] when compared to the O(ng" 11/2 (1+ Ig] 122) bound in Areces et al. (2024).
In this paper, we expand the scope of conditional coverage guarantees by achieving the best of both worlds from these two lines of prior work. Building on Gibbs et al. (2023); Jung et al. (2023), we provide coverage guarantees for overlapping groups while, in the spirit of Mondrian conformal prediction (Vovk et al., 2003), allowing grouping functions to depend jointly on both the covariates X,+1 and the label Yu+1- More generally, our guarantees hold for fractional groups, where membership is defined as probabilistic function over X and Y.+1. This added flexibility enables the modeling of subgroups based protected attributes that are not explicitly observed but can be inferred through covariates and labels (Romano et al., 2020a). We name our method Kandinsky Conformal Prediction! drawing inspiration from Wassily Kandinsky's 's compositions of overlapping geometric forms (see Figure 2), as we provide conditional coverage guarantees for groups that are fiexible, overlapping, and probabilistic.
To complement our main algorithm. which ensures training-conditie
validity, we also provide test-time inference algorithm that obtains expected marginal coverage that also takes randomness over the draws on calibration data. By extending Gibbs et al. (2023)'s approach to accommodate group functions defined over both covariates and labels, we obtain an expected coverage error bound of O(n However, this result comes at the cost of computational efficiency, as the algorithm needs to perform test-time inference that solves an instance of quantile
We note that the name Kandinsky Conformal Prediction coincides with that of an unrelated conformal prediction method for image segmentation (Brunekreef et al., 2024), which balances pixel-level and image-level calibration. Our technique instead focuses conditional guarantees of general conformal prediction.
2

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage
regression for every new test example.
guarantees for overlapping group structures. Prior work on 1. We study the most general formulation of group- conditional coverage guarantees in conformal prediction, handling overlapping groups and fractional group memberships that are defined jointly by covariates and labels. This conditional guarantee can be used to obtain valid coverage under general subpopulation distribution shifts.
overlapping group-conditional coverage primarily considers groups defined solely by covariates Xn+1- Barber et al. (2021) addresses this by assigning the most conservative prediction set to points in multiple groups. Our algorithm builds on the quantile regression techniques of Jung et al. (2023) and Gibbs et al. (2023), which compute per-example thresholds on non-conformity scores. Blot et al. (2024) extends Gibbs et al. (2023)'s technique to include group membership functions depending on both the label and the covariate, and they establish one-sided marginal coverage bound. We further provide two-sided training conditional bounds with a different algorithm. Additionally, Areces et al. (2024) establishes a lower bound on group-conditional coverage error rates. Since we generalize to group functions that depend on both covariates and labels, their bound applies to our setting and shows that our error rate is minimax-optimal.
Our contribution can be summarized as follows.
We propose Kandinsky Conformal Prediction, a method that is both computationally efficient and statistically optimal. Computationally, it requires solving single quantile regression over the vector space spanned by group functions. Statistically, it attains the minimax-optimal group-conditional coverage error with finite samples.
3. We evaluate our algorithm on real-world tasks, including income prediction and toxic comment detection. Our results show that Kandinsky Conformal Prediction consistently achieves the best-calibrated conditional coverage while scaling effectively with the number of groups.
Thematically, our work is related to a long line of work in multi multi-group group fairness (Kearns et al., 2018; Hébert-Johnson et al., 2018; Kearns et al., 2019). In particular, our algorithm can be seen as predicting target quantile conditioned on covariates and labels while satisfying the multiaccuracy criterion (Kim et al., 2019; Roth, 2022).
Finally. our work advances the study of conformal prediction under distribution shifts between calibration and test data. Existing research largely focuses on specific cases, such as covariate shift (Tibshirani et al., 2019; Qiu et al., 2023; Yang et al., 2024: Pournaderi & Xiang, 2024) or label shift (Podkopaev & Ramdas, 2021). Plassier al. (2024) considers general shifts on both the covariate and label distributions. However, all of these approaches are designed for a single target distribution. By introducing a more general class of group functions that depend jointly on covariates and labels, we establish coverage guarantees that remain valid under broader distribution shifts over X' x V, including multiple potential target distributions.
1.1. Related Work
The literature on conformal prediction is vast, covering a range of coverage guarantees, methods, and applications. Several textbooks and surveys provide in-depth discussions (Vovk et al., 2005; Shafer & Vovk, 2008; Balasubramanian et al., 2014; Angelopoulos et al., 2024). A classical method is split conformal prediction (Papadopoulos al., 2002a; Lei et al., 2018), which ensures marginal coverage. A major advantage of conformal prediction is that the coverage guarantees hold regardless of the choice of non-conformity score functions. Meanwhile, another line of research explores specialized non-conformity scores for specific tasks, such as regression (Lei et al., 2013; Romano et al., 2019; Izbicki et al., 2020) and classification (Sadinle et al., 2019; Angelopoulos al., 2020; Romano al., 2020b).
2. Preliminaries
We consider prediction tasks over X' x V, where X' represents the covariate domain and y represents the label domain. y can be either finite for classification tasks or infinite for regression tasks. Unless stated otherwise, we assume that the observed data is drawn from a distribution D, defined over X' x y. We consider potentially randomized prediction set functions, denoted by C(X:e), where the randomness is introduced by a random variable s that is independent of (X,Y). We further assume that the randomness of the conformal prediction algorithm depends n independent random variables e; that are independent of the dataset {(x,, YE))s(())
Our work is closely related to the growing body of work on conformal prediction that establishes coverage guarantees conditioned on events involving the test example (Xa+1, Yn+1). A fundamental class of such events corresponds to disjoint subgroups. For instance, Mondrian conformal prediction (Vovk et al., 2003) partitions the space X y into disjoint regions, encompassing class-conditional (Löfström et al., 2015; Ding et al., 2023) and
(Romano et al., 2020a) conformal prediction as special cases.
We introduce Kandinsky Conformal Prediction as an extension of the Mondrian approach, providing coverage
3

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conddttonal Coverage
Let (1 a) be the target coverage level, where E (0, 1). We can now restate the definition of training conditional validity to account for the randomness of the algorithm and the prediction set function. Specifically, this requires that for any f the training algorithm returns a (potentially randomized) prediction set function such that, with probability - å over the draws of the calibration dataset {(X,, Rejn and the randomness of the conformal prediction algorithm, captured by jej). the following holds:
3. Kandinsky Conformal Prediction
In this section, we describe the components of the Kandinsky conformal prediction framework. We will first present our method by extending the conditional conformal prediction algorithm by Jung et al. (2023) to work with classes of finite-dimensional weight functions of the form W { 3 E ]. where & X' x y + I. is a basis that is defined according to the desired coverage guarantee. After presenting our main result, we will demonstrate how this conformal prediction method can be tailored to different applications. The detailed proofs of our results from this section are in Appendix A.1.
P [[K++1 E C(Xn+1iSn+i) (i,, ~ x1-a a,
(2)
for some 6 in 1).
Given a coverage parameter o E (0, 1), predictor f X' + V, and a calibration dataset of n examples D = {(X,, Yi) drawn independently from a distribution D. the objective of Kandinsky conformal prediction is to construct (possibly randomized) prediction set function C(-) such that, with high probability over the calibration dataset D and the randomness of the method that constructs C, for every w E W
We use weight functions w : X x y + IR to model our conditional coverage guarantees. For any weight function w, measure the error of fixed prediction set function C by its weighted coverage deviation:
wCD(C, w) = (X, (Y C(Xie)) - (1 -))
where the expectation is taken over the test point (X, Y), drawn from D, and E, the internal randomness of C.
wCD a w) = O.
Given the predictor f. we use a non-conformity score function S : X y - to measure how close the prediction ((x) is to the label y for any data point (I, y) X' V. As is common in conformal prediction, our method ensures the desirable coverage for any score function S. However, in our more general framework, we allow for the use of a randomized score function to break potential ties in quantile regression, while kceping the assumptions about distribution D minimal. We implement this through randomized score function S X' x y R + R that takes input the covariates, labels and some random noise IR
Many conformal prediction methods require calculating quantiles of a distribution.
Definition 2.1 (Quantile). Given distribution P defined on R. for any r E [0, I] the r-quantile of the distribution P, denoted q. is defined as
q = PR: < T.
Our more general framework performs quantile regression by solving pinball loss minimization problem. By Lemma 2.3, in the special case where we compute the largest value in IR that minimizes the sum of pinball losses over set of points, we obtain a (1 a) quantile of the set.
Our method consists of two steps: one is performed during training, and the other at test time. Similar to Jung et al. (2023), the first step is a quantile regression on the scores of the n data points in the calibration dataset, {S(X,, be)ej For randomized score functions, we work with the set of randomized scores (S(X,, Yi, [e) where for every point is drawn independently from a distribution Dm- In Algorithm 1, we compute (1 - a>- "quantile function" q. This q is a weight function from W that minimizes the average pinball loss of the n (randomized) scores with parameter ax
Definition 2.2 (Pinball Loss). For given target quantile 1 - a, where a E [0, 1], predicted value 0 E IR and score 8 E R, the pinball loss is defined as
(0, = [ (1 a) -), 0), if 2 0, a(l
a((--)) - s).
if s < A.
Lemma 2.3 (Koenker & Bassett, 1978)). Let a be a parameter in (0, 1), and let {8i]se(n) be a set of n points, where for all i E [n]. 8, E IR Then, the largest 0" E RR such that
At test time, we run the second step that constructs the prediction set for given point with covariates X,+1- For fixed estimated quantile function T. the prediction set produced by Algorithm 2 includes all labels y E y whose (randomized) score (with noise En+1 drawn from Dm)) is at most q ((nn1..)) y). For more details about the computation of Algorithm see Appendix A.3.
0" E arg min BER (E(x)
(la
a (1 - -q-uaniille of (e)))))))
4

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditionaa Coverage
Algorithm 1 Quantile Regression of Kandinsky CP
Jung et al. (2023) derive concentration results directly for the pinball loss, which leads slower convergence rate of ((d log n/n)
Input: ((X;, ke))e W, and S
I: For all i e [n]] draw E; independently from Dm-
2: Find
As a corollary of Theorem 3.1, we derive bound on the expected coverage deviation of C, with the expectation taken over the randomness of the calibration dataset and the noise in the randomized scores.
Σ 1=1
i E arg min
NEW n2
Corollary 3.2. Lei a. a, be specified as in Theorem 3.1 and consider the same assumptions on ((,,,, Ei))))) S, and & in Theorem 3.1. Then, there exists an absolute constant C such that the (randomized) prediction set C, given by Algorithms and 2, satisfies
Return: Quantile function 7
Algorithm 2 Prediction Set Function of Kandinsky CP
Input: X T. and 5
1: Draw En+1 independently from Dm-
WCD a, wa)
2: Set C(Xx+11En+1)
ED
sup WyEW
|
S C
+ n
{v: (X:5((ntiB S ((x
where D is the calibration datasel {(X;, YE) and E is the corresponding noise (Eilve()).
Return: C(X,+1;enn)
Weight Functions Defined on the Covariates Areces et al. (2024) show that when the covariate-based weight class W contains a class of binary functions with VC dimension d, equal the dimension of the basis o, then the convergence rate of the expected coverage deviation is at least O( - a)/n). This means that for n > d, the rate in Corollary 3.2 is asymptotically optimal. In Appendix A.2 we compare our upper bounds with prior work.
Our main result is stated in Theorem 3.1, where we prove that, under the assumption that the distribution of the randomized score S conditioned on the value of the basis 4 is continuous, the weighted coverage deviation of C converges to zero with high probability at rate of O(Vd/n + d/n), where d is the dimension of &. When the distribution of S(X,Y) ( Y) is continuous, this theorem holds for the deterministic score function S, since setting (1x y, S(z y) satisfies the assumptions.
3.1. Applications
Theorem 3.1. Let parameters a, (0.1), and W ( 3 [Rd] denote class of linear weight functions over bounded basis & : X x y + R.. Without loss of generality, assume [1, v) S for all y. Assume that the data {(X,, Hie are drawn i..dd from a distribution DD [Ei]ve[w) are drawn i..d from a distribution Dmn. independently from the dataset, and the distribution of S (X,Y,e) ((X, Y) continuous. There exists an absolute constant C such that, with probability at least 1 8 5 over the randomness of the calibration dataset {(X,, Yi) and the noise {Ei)eejnj the (randomized) prediction set C given by Algorithms I and satisfies, for every w3- = 3.
Kandinsky conformal prediction a general framework that can be specialized to obtain several types of weighted or conditional conformal prediction. The choice of the appropriate basis & and, consequently, the weight function class W depends the desired coverage guarantee. In this subsection, we explore how Kandinsky conformal prediction can be applied to several scenarios, including group-conditional conformal prediction, Mondrian confor- mal prediction, group-conditional conformal prediction with fractional group membership, and conformal prediction under distribution shift.
Group- Conditooniiiioal Conformal Prediction Suppose we want to achieve the target coverage (1 ax) for every group of points G C X x y within a finite set of potentially overlapping groups G. Let Te (C((C) be the probability that the true label is included in a fixed prediction set C, conditioned on the datapoint (Xn+1, Ya+1) belonging to some group G. Formally, with the calibration dataset D {(X,, Y:) and the corresponding noise E {Es)iejm) let
a, a,
d - +- mmxxfa,
d
2m Am(4d/d)
||
cv
As a sketch of the proof, we first establish a connection between the subgradient of the empirical pinball loss and the empirical weighted coverage. We then prove a concentration result for the weighted coverage. contrast, Roth (2022);
TC(C)= = IP(Y+1 E C(Xn+1jen41) D, E, (Xn+1, Yat1) E GJ.
5

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conddttonal Coverage
We want to ensure that for every G E 9, (c(C)= 1 a. Here we can define @ be [g] -lldimeesillaa vector that has an entry [((x, 2) E G} for every G' E G. Corollary 3.3 provides the rate at which (C) converges to (1 al) when C is constructed by Algorithms and 2. For conciseness, we define FG == [P(( Xu+1) E G].
The simplest example of the statistic & is éxy(X,) Y) (X, Y). In practice, if pretrained + is not available, we may use the protected attributes Z in calibration data to estimate the probabilities in Φ. In some cases, we may only have indirect access to the covariates through the pretrained predictor f(X). Then, we can construct the statistic as O Y) = ()(),, Y). In general, Corollary 3.4 shows that our algorithm ensures group conditional coverage if o is sufficient statistic for the score function, which is satisfied by both ΦxY, OFY.
Corollary 3.3. Let parameters a, E (0,1), and W (ggg B E G} : 8G E RR, VG E G}. Assume Y,, (e are i.i.d. samples. Under the same assumptions on S and & in Theorem 3.1, there exists an absolute constant C' such that, with probability at least 1-6 over the randomness of the calibration dataset {(X,, (x),,,))eei Yejn) and the noise (Ei]selml the (randomized) prediction set C given by Algorithms I and satisfies, for all G E G.
For our theoretical result, we assume that we already know these conditional probabilities, a y). for all G E g, and that the calibration and the test data do not include unobserved attributes. Corollary 3.4 shows that by constructing C' according to Algorithms 1 and 2, the coverage converges to (1 a) an ((V + (9l/n) rate. For brevity, we define T == P(Zn+1 G].
(C) -aaalss
1
C G n
2 Inn(4 ( maxfa, 1- v)v 7
Corollary 3.4. Let a, E (0, o(X,Y) be a sufficient statistic for S, such that S is conditionally independent of X,Y given o, and W [Eoeg 2c : AG E RR, G g). Assume {(x,, Y,, ei)ee(n))))) are i...d samples. Under the same assumptions on $ and & in Theorem 3.1, there exists an absolute constant C such that, with probability at least 1- 8 over the randomness of the calibration dataset {(,,, Ve)een and the noise (Eshre(n). the (randomized) prediction set given by Algorithms and 2 satisfies, for all G E g.
T
n
Mondrian Conformal Prediction A special case of group-conditional conformal prediction is Mondrian conformal prediction, where groups in G are disjoint and form a partition of the domain X' x y. Since each (X,, Y;) in the calibration dataset belongs to exactly one group in G, we can verify that Algorithm 1 computes a value $6 E IR for every group G independently. By Lemma 2.3, for every G E g. if AG is the largest value that minimized the pinball loss, then it is (1 -qaanttle of the scores of the calibration datapoints that belong to G. As result, for test point Xn+1, we construct the prediction set ((x,+1) by including every y where the score 5(X,+1 1; y, e) is at most the quantile BG corresponding to the group G' that contains (X.+113) 3). This method is the same as the one presented in (Vovk et al., 2003), with the difference that in that method, the quantiles are slightly adjusted to achieve the expected marginal coverage guarantee through exchangeability.
[CE(C) (1 (1-x)1
-a)l
g n
2 (ln(491/8
+ maxfaa, 1 -aty n
n
Distribution Shifts Kandinsky conformal prediction can also ensure the target coverage under class of distribution shifts, where the joint distribution over both the covariates and the labels can change. In this context, we assume that the calibration dataset {(x,, X)) is sampled i.i.d. from a source distribution D, while the test example (X,, Yn+1) may be drawn independently from another distribution Dr. The objective is to construct prediction set that satisfies
Fractional Group Membership In some cases, we are concerned with the conditional coverage in groups defined by unobserved attributes. Let Z be the domain of these unobserved attributes, and let D'. defined over X x y x 2, be the joint distribution of the covariates, the label, and the unobserved attributes. In this setting, 9 is a set of groups defined as subsets of Z. Let
ar, for a set of test distributions Dr. Given a weight function class W, Corollary 3.5 states that we can achieve the desired coverage for all distribution shifts Dr with its Radon-Nikodym derivative dFp (z, y) contained in W.
PD, (Ya41 E C(Xn411en-)) (Xi, Ei,eil
-0(C)= = P(Yn+1 E ((( D,E,, 2m-1 E G].
Then, we want to ensure that (C( s a for every G E G. To achieve this, set the hasis of the weight function class the probability of Z G given statistic s(X, Y). For every G E G.
Corollary 3.5. Let and ê be parameters in (0, 1), and W (B::)T3: 3 E Rd4 denote a class of linear weight functions over a bounded basis t b: X x y + Rd. Under the same assumptions on ((X,, Y,, Vi,ee))eetn) S, and $ in
oa(a.v) = P|Z e G | o(z,8)]
6

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage
Theorem 3.1, there exists an absolute constant C such that, for every distribution Dy such that drpr AFD W and dFrr (x,y) S B for any I E X and E y. with dPD probability at least 1- over the randomness of the calibration dataset {(X,, (e)inn) and the noise (Estre(m), the (randomized) prediction set C, given by Algorithms 1 and 2, satisfies
the expected weighted coverage deviation is bounded by (ddnn).
Theorem 4.1. Let a be a parameter in (0, and let W ( R denote a class of linear weight functions over basis क : X data (E),,)))) are drawn i.i.d. from distribution D. [[es)ie/+11] are drawn i..dd from a distribution Dim. independently from the dataset, and the distribution of $ (X,Y,e) Y,)) ((X, Y) is continuous. Then, for any w E W. the prediction set given by Algorithm 3 satisfies
Rd. Assume that the
IP[Yn+1 E ((( | (X,, Y2, Yireei - a)l
d d C
maxfa, 1 - a] 2 2l1(4/0)
SB
++ n n
n
d ED+ max loo( X2 Yi)1 [EE|++]]
E EDD,E a, w)ll
n ++
where (X++1, Yn+1) are drawn independently from the distribution Dr, and En-1 are drawn independently from the distribution D,
where D is the calibration dataset {(x,, Vil E is the corresponding noise {Ei]ie(n) and D+ the full dataset {(,,, Yi) ri(n++1)-
4. Test-time Quantile Regression
Algorithm is significantly more computationally expensive than Algorithms and 2, as performs multiple quantile regressions per test point. Let Typ denote the time required for a single quantile regression. In naive implementation, computing the prediction set scales as 0(22 TTp) Even if for certain score and weight functions the construction of the prediction set avoids enumerating V the complexity remains (TTr)) per test point.
In this section, we explore an alternative quantile regression- based algorithm that extends the method proposed (Gibbs al., 2023) weight function classes over X' x V. This method, detailed in Algorithm is more complicated than Algorithms 1, 2 and performs both steps during test time.
Specifically, given the covariates of a test point X Algorithm 3 computes a separate quantile function dy for each label y E y by minimizing the average pinball loss over the scores of both {(x,, )e)) and (X,+1, y)- Since Xn+1 is required for the quantile regression, this step is performed at test time. The prediction set C produced by Algorithm 3 includes all labels y y where the score is at most the label specific quantile, evaluated at (Xn+1,
5. Experiments
We empirically evaluate the conditional coverage of Kandinsky conformal prediction on real-world tasks with natural groups: income prediction across US states (Ding et al., 2021) and toxic comment detection across demographic groups (Borkan et al., 2019; Koh et al., 2021). The data is divided into a training set for learning the base predictor, calibration set for learning the conformal predictor, and a test set for evaluation. We repeat all experiments 100 times with reshuffled calibration and test sets.
Algorithm: 3 Test-time Quantile Regression
Input: X {(X,, kEj)) W, and 5
1: For all i E [n + 1]. draw e, independently from Dm
2: Set ((X
{v: 3(X (X,t,,)))))
Algorithms. We implement Kandinsky conformal predic- tion described in Algorithms 1 and 2 for probabilistic groups. According to Corollary 3.4, we estimate the basis function &G (see Equation (3)) using a Gradient Boosting Tree classifier. Kandinsky (XY) uses the covariates and the label as input to learn the basis (ø = (X, Y)), while Kandinsky (FY) uses the output of the predictor and the label (Φ = (f(X), Y)). We compare this approach with conformal
where
By E Earg min 1
Σ
(a(w(X, Yi), S(x,, e.))
wEW
+ 1=1
Calww(Xnn w). 3, (( en+1)))
n n+1
split conformal prediction, prediction (Löfström et al., 2015) (where labels are discrete), and conservative conformal prediction (Barber et al., 2021 1), which estimates the (1 (1-a) - of scores for each group and constructs sets using the score threshold determined by the maximum quantile.
Return: C(X
For the weight functions W (3))) B E R where : X x y + Rdd under the same assumptions about the data and the distribution of $ + in Theorem 3.1,
7

---

Kandinsky Conformal Prediction: Beyond Class- and Govariate-Conditiona Coverage
Group Conéitional Miseovergge
A Aveag C9
0.12
0.020
Kandinsky (XV)
0.10
Kundinsky (XY)
0.015
Kandinsky (FY)
Kandinsky (FY)
0.310
Conservative Split
0.08
Split
Conservative
0.005
23
15
Groups
Groups
ACSIncome.
The distribution of group average
The distribution of group conditional (b) miscoverage (mean over runs) across different groups. Whiskers extend to min and max values. Target miscoverage is 0.1.
ACSIncome.
(a) coverage deviation across 100 runs.
0.16
Prodiction Set Stze
0.27
0.14
Group Avgage
0.2
Kandinsky (XY)
1010
Kandinsky (FY)
0.25
Kandinsky (FY)
0.08
Class Conditional Conservative
Conservative
0.66
024
Split
0.94
Split
002
Groups
Group Average Sample
ACSIncome. The distribution of average prediction set sizes across 100 runs.
CivilComments. The distribution of group average coverage deviation 100 runs.
(c)
(d)
Figure 3: Main results. (a)b)(c) ACSIncome. We vary the number of groups in calibration and test sets while controlling samples per group. (d) CivilComments. We redistribute samples between calibration and test sets to vary the number of calibration samples.
Metrics. Given m test samples, we measure the conupcooniiional miscoverage M(G,C) for group G and prediction set C.
10,000 individuals per state to train base Gradient Boosting Tree regressor and the basis weight functions for our method. We sample 4,000 individuals per state for calibration and 2,000 individuals for testing. The experiment is performed over 31 states, each with at least 16,000 samples. We use the Conformalized Quantile Regression score function (CQR) (Romano et al., 2019). For further details, see Appendix C.I.
M(G.C) Disnt1 (Y, C(X, e:) (Z, E G)
Eutm
1 (Z, E
We compute the group average coverage deviation CD(C).
Kandinsky conformal prediction achieves the best group average coverage deviation, shown in Figure 3(a). Weight functions based predictors and labels (FY) slightly outperform those based on covariates and labels (XY), as learning group classifier with lower-dimensional input is easier with finite samples. Both Kandinsky algorithms maintain stable average coverage deviation as the number of groups increases. Figure 3(b) shows that our approach achieves the minimum difference between the maximum and minimum miscoverage across various groups. All algorithms exhibit larger gap with more groups, aligned with the universal bound on the maximum group coverage deviation (Corollary 3.4), which scales inversely with the relative proportion subgroups. Kandinsky (XY) produces prediction sets with moderate and stable sizes for various groups numbers, while the size of Kandinsky (FY) scales with the number of groups, shown in Figure 3(c). This reveals tradeoff between the computational efficiency of
CD(C) = Σ IM(G,C)-o -
1
GEB
We also evaluate the prediction set size. For real-valued labels, we divide label domain into 100 evenly spaced bins. We count the number of bin midpoints that fall within the prediction and estimate its size by multiplying this number by the bin width.
5.1. ACSIncome: A Regression Example
We predict personal income using US Census data collected from different states, aiming to achieve the target coverage conditioned on each state. The state attribute is omitted from the covariates and labels of the test points. We investigate the scalability of the algorithms by varying the number of groups in the calibration and test set, while controlling the number of samples per group. Specifically, we sample
8

---

Kandinsky Conformal Prediction: Beyond Class- and Lovariate-Conditionn Coverage
Kandinsky (FY)
Group Conditional Miscovengee
Class Conditional Conservative Split
22
Liaet alople
besc paople
too7 depple
Juud repple
mostle after sepple
LCarT yo ANp seople
algine pi 2010 nample
waile 207 lample
2018 Sapple
Hoio staple
sontia Ain jiddaapple
Stek 1ng aakaaapiaa
decam 1167
LCBTV RRS ineple
wiil mepple
200
Conditional viscoverage for each group. Target miscoverage is O.I. Error bars are
(a) standard deviations of 100 runs.
1.50-
Prediction
1.00
Kundinsky (FY)
6.50
Class Conditional Conservative
Split
600
Liael analee
bakel mapples
fest smmple
sya supplee
LamT
20e
2017 compee
2010 staple
samale
1854 sumpler
Blok 13sk
Lamo 651
yeu
supple
(b) Commenmsssss. Average prediction set sizes for each group. Error bars are standard deviations 100 runs.
Figure 4: Group-wise metrics CivilComments. There 4000 calibration samples per group average. We annotate the calibration sample size for each group. Groups with positive labels (toxic) represented by y:
learning weight function class and the effectiveness of the prediction set.
Kandinsky conformal prediction achieves the best group average coverage deviation when the calibration set contains an average of over 500 samples per group, as shown in Figure 3(d). Class-conditional conformal prediction achieves the best performance with 250 samples per group. However, unlike our approach, its coverage deviation does not improve with larger sample sizes. This is because Kandinsky considers the full set of groups, which are more fine-grained than classes. In Figures 4(a) and 4(b), we examine conditional miscoverage and prediction set sizes for each group under the setting of 4000 group average samples. Overall, Kandinsky generates prediction sets with conditional miscoverage closest to the target level for most groups while maintaining moderate sizes. We achieve the best calibrated coverage for groups with more than 2000 samples.
5.2. CivilComments: A Classification Example
The task is to detect whether comments on online articles contain toxic content. Demographic attributes, such as gender, religion, race, and sexual orientation, are sometimes mentioned the comments, According to the Koh et al. (2021) benchmark. there are 16 overlapping groups jointly defined by eight demographic attributes and two labels. We consider setup where the conformal prediction algorithm has only indirect access to the training data through given base predictor, a DiStiBBERT model finetuned on the training split. Kandinsky conformal prediction (XY) cannot be applied, and the weight functions of Kandinsky (FY) are trained on the calibration set. We use the randomized Adaptive Prediction Sets (APS) score function (Romano et al., 2020b; Ding et al., 2023). We also evaluate the algorithms' adaptability to varying calibration sample sizes by redistributing samples between the calibration and test sets. See Appendix C.2 for more details.

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conddttonal Coverage
Acknowledgements
Brunekreef, J., Marcus, E., Sheombarsing. R., Sonke, J.-J., and Teuwen, J. Kandinsky conformal prediction: efficient calibration of image segmentation algorithms. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4135-4143, 2024.
KB's research is supported by NSF awards CCF-2311649, CNS-2232692 and CNS-2247484.
Impact Statement
Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 6478-6490, 2021.
In this paper, we introduce Kandinsky Conformal Prediction, which extends conformal prediction to provide coverage guarantees across a broader class of overlapping and fractional groups. This framework addresses fundamental challenges in fairnsss and distribution shift, ensuring robust, well-calibrated uncertainty quantification across diverse subpopulations. By maintaining computational efficiency, our method strengthens the technical foundation for reliable predictive modeling in real-world applications.
Ding, T., Angelopoulos, A., Bates, S., Jordan, M. I., and Tibshirani, R. Class-conditional conformal prediction with many classes. In Advances in Neural Information Processing Systems 36: Annual Conference Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Neural
References
Angelopoulos, A.. Bates, S., Malik, J., and Jordan, M. I. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. 14193, 2020.
Gibbs, I., Cherian, J. J., and Candès, E. J. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305. /2616, 2023.
Angelopoulos, A. N., Barber, R. F., and Bates, S. Theoretical foundations of conformal prediction. arXiv preprint arXiv:2411. 1882, 2024.
Hébert-Johnson. Ú. Kim, M. P., Reingold, O., and Rothblum, G. N. Multicalibration: Calibration for the coompurationally-ddeniiii J. G. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockhelmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1944-1953, PMLR, 2018
Areces, F. Cheng, C., Duchi, C., and Rohith, K. Two fundamental limits for uncertainty quantification in predictive inference. In Agrawal, S. and Roth, A. (eds.), The Thirty Seventh Annual Conference on Learning Theory, June 30 July 3, 2024, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pp. 186-218. PMLR, 2024.
masses. In Dy,
Izbicki, R., Shimizu, G. Y., and Stern, R. B. Flexible distribution-free conditional predictive bands using density estimators. In Chiappa, S. and Calandra, R. (eds.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pp. PMLR. 2020.
Balasubramanian, V., Ho, S.-S., and Vovk, V. Conformal prediction for reliable machine learning: theory, adaptations and applications. Newnes, 2014.
Barber, R. F., Candes, E. J., Ramdas, A., and Tibshirani, J. The limits of distribution- free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455-422, 2021.
Jung, Noarov, G., Ramalingam, R., and Roth, A. Batch multivalid conformal prediction. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Blot, V., Angelopoulos, A. N., Jordan, M. I., and Brunel, N. J. Automatically adaptive conformal risk control. arXiv preprint arXiv:2406.177 2024.
Borkan, D., Dixon, L., Sorensen, J.. Thain, N., and Vasserman, L. Nuanced metrics for measuring unintended bias with real data for text classification. In Amer- Yahia, S., Mahdian, M., Goel, A., Houben, G., Lerman, K., McAuley, J. J., Baeza-Yates, R., and Zia, L. (eds.), Companion of The 2019 World Wide Web Conference, WWw 2019, San Francisco, CA. USA, May 13-17, 2019, pp. 491-500. ACM, 2019.
Kearns, M., Neel, S., Roth, A., and Wu, Z. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2564-2572. PMLR, 10-15 Jul 2018
10

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conddttonal Coverage
Kearns, M., Neel, S., Roth, A., and Wu, Z. S. An empirical study of rich subgroup faimess for machine learning, In Proceedings of the Conference Fairness, Accountability, and Transparency, FAT* '19, pp. 100-109, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450361255.
Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. Inductive confidence machines for regression. In Machine learning: ECML 2002: 13th European conference on machine learning Helsinki, Finland, August 19-23, 2002 proceedings 13, pp. 345-356.
Springer, 2002a.
Kim, M. P., Ghorbani, A., and Zou, J. Y. Multiaccuracy: Black-box post-processing for fairness in classification. In Conitzer, V., Hadfield, G. K., and Vallor, S. (eds.), Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, AIES 2019, Honolulu, HI, USA, January 27-28, 2019, pp. 247-254, ACM, 2019.
Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. Inductive confidence machines for regression. In Machine learning: ECMI. 2002: 13th European conference on machine learning Helsinki, Finland, August 19-23, 2002 proceedings 13, pp. 345-356. Springer, 2002b.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., VanderPlas, J., Passos, A.. Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, Scikit-learn: Machine learning in python. J. Mach.
Koenker, R. and Bassett, G. Regression quantiles. Econometrica, 300,00 1978.
Koh, P. W., Sagawa, S., Marklund, H., Xie, S. M., Zhang, M.. Balsubramani, A.. Hu, W., Yasunaga, M., Phillips, R. L., Gao, I., Lee, T., David, E., Stavness, I., Guo, W., Earnshaw, B., Haque, I. S., Beery, S. M., Leskovec, J., Kundaje, A., Pierson, E., Levine, S., Finn, C., and Liang, P. WILDS: benchmark of in-the-wild distribution shifts. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 5637- 5664. PMLR, 2021.
Learn. Res., 12:2825 2830, 2011.
Plassier, V., Kotelevskii, N., Rubashevskii, A., Noskov, F. Velikanov, M., Fishkov, A., Horvath, S., Takac, M., Moulines, E., and Panov, M. Efficient conformal prediction under data heterogeneity.
International Conference on Artificial Intelligence and Statistics, pp. 4879-4887. PMLR, 2024.
Podkopaev, A. and Ramdas, A. Distribution-free uncertainty quantification for classification under label shift. In Uncertainty in artificial intelligence, pp. 844-854 PMLR, 2021.
Lei, J. and Wasserman, L. Distribution-free prediction bands for non-pan oonaamametriic regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76 (1):71-96, 2014.
Pournaderi, M. and Xiang, Y. coniiiinaconiiiionall coverage bounds under covariate shift. arXiv preprint arXiv:2405. 2024.
Lei, J., Robins, J., and Wasserman, L. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):278-287 2013.
Qiu, H., Dobriban, E., and Tehetgen Tchetgen, E. Prediction sets adaptive to unknown covariate shift. Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(5):1680-1705, 2023.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. Distribution-Fi free predictive inference for regression. Journal of the American Statistical Association, 113653):1094-1111 2018.
Romano, Y., Patterson, E., and Candès, E, J. Conformalized quantile regression. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' Alché-Buc, F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3538-35335555 -3488, 2019.
Liu, J., Wang. T., Cui, P., and Namkoong, H. On the need for language describing distribution shifts: Illustrations tabular datasets. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Romano, Y., Barber, R. F., Sabatti, C., and Candès, E. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2(2):4, 2020a.
Löfström, T., Boström, H., Linusson, H., and Johansson, U. Bias reduction through conditional conformal prediction. Intell. Data Anal., (9(6) 2015.
Romano, Y., Sesia, M., and Candès, E. J. Classification with valid and adaptive coverage. In Advances in Neural Information Processing Systems 33: Annual

---

Kandinsky Conformal Prediction: Beyond Class- and Lovariate-Conditiona Coverage
Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020b.
Roth, Uncertain: Modern topics in uncertainty estimation. Unpublished Lecture Notes, pp. 2, 2022.
Sadinle, M., Lei, J., and Wasserman, L. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223-
234, 2019.
Shafer, G. and Vovk, V. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
Shalev-Shwartz S. and Ben-David, S. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
Tibshirani, R. J., Barber, R. F., Candès, E. and Ramdas, A. Conformal prediction under covariate shift. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d' A'Achh-BBuc F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14. 2019, Vancouver, BC, Canada, pp. 2526-2536, 2019.
Vovk, V. Conditional validity of inductive conformal predictors. Asian Conference on Machine Learning, pp. 475 490. PMLR, 2012.
Vovk, V., Lindsay, D., Nouretdinov, I., and Gammerman, A. Mondrian confidence machine. Technical Report, 2003.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic Learning in Random World. Springer, 2005. ISBN 978-0-387-22825-8.
Wainwright, M. J. High-dimensional statistics: A non- asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
Yang. Y., Kuchibhotla, A. K., and Tehetgen Tchetgen, E. Doubly robust calibration of prediction sets under covariate shift. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp. qkae009, 2024.
12

---

Kandinsky Conformal Prediction: Beyond Class- and Lovariate-Condittonal Coverage
A. Proofs and Remarks from Section 3
In this section, we present the omitted proofs from Section and provide some further discussion about the coverage and the computational complexity of Kandinsky conformal prediction.
A.1. Proofs from Section
We first show in the following Lemma that for a fixed w E W, the expected weighted coverage deviation is bounded with high probability. Note that this statement provides bound for single weight function.
E R denote a class of linear weight functions over bounded basis & : X y - Rdd. Assume that the data {(X,, Ye))e((+11) are drawn ii.d from distribution D. {Eiheen+1) are drawn i.i.d from a distribution D, independently from the dataset, and the distribution of S (X.Y,e) ((X,Y) Y) is continuous. Then, there exists absolute constant C such that, for every w E W, with probability at least 1 - 8 over the randommess of the calibration dataset {(X,, Yi) and the noise (Eile(nn) the (randomized) prediction set C, given by Algorithms and 2, satisfies
Lemma A.1. Let a and be parameters in (0, 1), and W = {
((x,,))D Iw (1 E c((:=)) - -1 (1-a)) (1-a)]]| s |wllo (c
+ d + mmxxfa, 1 - n
2 2ln(4/))
a/V
Proof. Denote 3 (,,,,, E,) by 3r. Then {(x, Yú, Si) are independent and identically distributed.
Consider the function I(n) # E. la (Txi,, Vi) + ( 5.). 7 E TR, which is convex because (a (:, is convex for each
For any W, since & + nw W, the subgradients of L(n) 17 0 satisfy
a 1( ((,,, Ki). Y. # S.
aL(n)) 0-
(X, Y3) 91
a; E - 1,a]:
Y,) = S
Therefore, there exist aj E |a - a, E [n] such that
Σ
w(X, Yi) (a aa- ((xx)))))))) +
Σ
Y,) =.
This implies
Σ n
1 (X2, Yi) (a- (3. q(x, x.)x
Σ
w(X, (a az))
(4)
n2 ((X..)))=
[(Xx..)) 1o0
(5)
n
For the left hand side of Equation (4), we consider the function classes
H1 (z, s) (9(2.)) s< <3 qe wew] ( <-)) 3 F*) = ()
H2 (22 y,
w(x,
(x, h m1).
(1 v)
Under the mapping (z. s) +
E Rd+1, H2 is the subset of all homogeneous halfspaces in R441, with the
{ normal vector !
Therefore, the VC-dimension of Hi is at most d +++ 1.
13

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Condittonal Coverage
For samples D ((X,, Y, (e(n) the empirical Rademacher complexity of function class H restricted to D is defined
R(H D)
B
sup
o Yr, 3.)
where random variables in independent and identically distributed according to Plo, 1] =Poo, -1] 1
Wainwright (2019) (Example 5.24) gives an upper bound of the Rademacher complexity for VC classes. There exists an absolute constant C", such that
R(H o D)
Ea n
sup hEH1
Σ
(X, Y,, 3.)
sC' sCv"
d+1 S C'
2d
n
Next, we compute the empirical Rademacher complexity of H2 restricted to D. For any h h² E Hi.
[w(2, (a h(r,v,))) w(x, h1(x,,,))) s ||o]l [M(r,, v, 8)
According to the contraction lemma (Lemma 26.9 in Shalev-Shwartz Ben-David (2014)).
R(H2 o D) < || R(H D) C'11w]ll 2d m.
Therefore, we have universal generalization bound for the functions in H2- The functions in H2 are bounded by max 1- || According Theorem 26.5 in Shalev-Shwartz & Ben-David (2014), with probability at least 1 8 over the randomness in = {(X,, Y,, (E))) for all E H2.
h h(x, Y.) s 2Ed (R(H2 o D) + max fa, 1 - a} || 2 2l((2/))
E S
1=1
2d + max (a, 1 - aa} |100 2 2ln(2/5)
200'
n
Symmetrically, we can replace h with -h in the class H2. Since R(H2 D) R(- D). with probability least 1 - 5, for all h H2,
1 Σ Y, - -B x s 20
2d + max {a, 1 at 11 2ln(2/0)
n
Taking the union bound, with probability at least 5 over the randomness in D, for all h E H2.
E [x) 1 Σ M(X, S.)
2d + max fa, - aa ||
2ln(4/8)
22C'||
n
By expanding functions in H2 h(x y, 8) = w(x, (a (g(2,0) <<0)) where a W, with probability least
1 8 over the randomness in D. for all W.
(w((
Σ w w(X,, Yi) ((x,,,)) 3, 33 -((x))))
E
1 v) a - Σ
3<0})]
w(X,, (a-1 (1 - 3, <<)))
E
2d + max {a, 1 - at ||l||
2 2ln(4/5)
20" 10/1lloo
14

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conddttonal Coverage
In partieular, this inequality holds for By plugging in Equation (4) and Equation (5),
E EIX,Y)DDEWD. D2 ( 1 3 [(x,)) (1 (1- -1-ai)]]
Xi Yi) (a- - 1 Yi) - 3, 3<<0}) 20" 1wlloo
2d + max {a, 1 - a)) ||l|lo
2 2ln(4/))
2d + max fa, 1 - a) |1llwlaa 2ln(4/0)
(6)
Σ 1 (.) =
Yi) =Bi]lu(X, l +220||ulla
Σ 2 ((xx)))))) = 3.} + 200"|l/lloo
2d
max fa, 1 - ai |||||| 00 2m(44/)
Theorem 3 in Gibbs et al. (2023) provides an upper bound for quantity similar to Σ 1 ((xx)) = 3 under
different assumption that the distribution of $ is continuous. We will follow similar proof technique, but we assume that the distribution of $ t is continuous.
There exists 3 E TRd such that (())TB.
((X,.))) = 2d}
P
E
x (X,, Y,) 3.} 2 d+1
V(. Yn)
E
31 S ja+t
$(X1, Vi), $ $(x Yn)
E
Σ
P
(X,, 3 S,
$(X,, Y1), $(X Yn)
15h c.. SJetiSn
E
Σ
(n:..., Sj RowSpace ([ ,i),..,, o (Xia11 Yie1)))
15 K... <Jd+iIn
(()1,V)) D(Xm: Vn)
0.
The last equation holds because the distribution of (S,,...,3,,, (X1,, Yi.,... D(Xn, Yn) continuous, and
RowSpace Y()),,,,,,. ((X Yiar)) )]) is at most dimensional while (5,,..., 35,,, is (d+1)-dda dimmenional vector. Therefore, with probability 1,
Σ ((Xx)))) 3.} <
Plugging the inequality into Equation (6), with probability least 1 over the randomness in D,
B(X.Y) (n (1 {5 <(xx)))) (1 (n-a))]
2d + max fa, - a) !
2lm(4/0)
||
+20"
15

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Condittonal Coverage
Using Lemma A.1 and a union bound, we prove high probability bound the expected coverage deviation for all weight functions in W.
Theorem 3.1 (Restated). Let a and be parameters in (0, 1), and w = {2())* : E R4) denote a class of linear weight functions over a bounded basis + X'' x y + IR Without loss of generality, assume [| y) le S 1 for all i y- Assume that the data {(X,, he(n) are drawn i.i.d. from distribution D, {Ex)ie(m) are drawn i..d. from distribution Pm- independently from the dataset, and the distribution of 3 (xX, Y,,)) (x, Y) is continuous. Then, there exists absolute constant C' such that, with probability at least 8 over the randomness of the calibration dataset {(X,, X)) and the noise {ex hejjj the (randomized) prediction set C, given by Algorithms and 2, satisfies
+ n (cv n
2 2 (n
(1 a))] s $11811
+ maxfa; 1 - ar)
for every w 3.
Proof. Let (()) (.)()).... ,.())) where oj ERXy for S SjS S d. According to Lemma A.1, for all 1 s $ d.
with probability at least - 5/d,
BIX.YDDDDDD (,, ( -1 -1 (1-a))]] s sc / d d n n
2 21n ll(4///))
+ max(a; 1
adj
n
Then, have the union bound. With probability at least 1 6, for all S S d.
d d [(x,Y) (X, c(x:e)) (1 a])] s s
2 2 (4d6//))
+ + max(a, 1 agv
n
71
For any W3 =B.-73.
E B(xYY) (x)(X, (1 (1 -(1 -11-))]|
(((XYY)DD (X, (x, Y) (1 (Y E c((ie)) - (1-a))11
d + n
2In(4d/8)
Σ 13,1-
C
+ max a)v
d
d + maxfa, 1 -at
2 2ln(4d/0)
11:111
c
n
Corollary 3.2 (Restated). Let a, 6, W, wy be specified in Theorem 3.1. Assume that ((2,, Yi) [E( are drawn i..d. from distribution D, {ex [ex)ie(++]] are drawn i.i.d. from distribution D.,. independently from the dataset, and the distribution of Š (X, Y, =) @(X, Y) is continuous. Then, there exists an absolute constant C' such that the (randomized) prediction set C, given by Algorithms and 2, satisfies
W) (X Y)
(1 c((:s)) - (1- -aa]
d d n sc
Ep,9
sup E(X,Y)-D,owD, WsEW
||
where the calibration dataset ((,,, He) and E' is the corresponding noise [Eiieen
Proof. According to Theorem 3.1, there exists an absolute constant C' such that, with probability at least over the
16

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Condittonal Coverage
randomness in D and E,
Wx((XY)
(1 (1 E c(X;e)) -1 -(1x)))((Laaa)) -
sup EW
E (xD,y)
11
W)((XY)
sup "ya W
5
1131/1
C² V + d n
2 2In(4d/0)
max 1
d
1 2ln(4/6)
C
V
maxfa, 1
n
n
n
Let the random variable MD.E sup ww D(x,Y)
(X.Y 1B
(1 E c(X;e)) - (1 (1-
We have
d + + max max(a, 1 (a,11aap a/y MD > C² V
2
+ max (ax, 1 - -aJy 2lm(4/8)
PD.
S S.
By inverting the bound, for 1 V d + max(ur 1 - -u)y 2lnd
n(t - C² V'V d maxfa, 1 - aty 2
PD.E\Mpa > t] s 4exp
2 2max 1 =x
Let C² V + 2 maxfa, -o 2ldd
Since MD.F 2 0,
t00 MM. > dt
ED [MDel =
1=0
+00
PD.E|MD,E > t| +
PD,E|MDE t|
1=0
|=1
d
2nd
s CVV V
+
+ maxfa, 1 1 Vtv
PDDE\MDE > f dt
1=1
d
2 lln d
+00
n(t - 1)²
CV
+
+ maxfa, 1 atv
4exp
dt
12max 1 - cx
d
2 d
8T
C'
+ + maxfa, 1 11-aa ot/
+ max 1 -cad n
n
n
$ C'' + V2+ + V 8T
Corollary 3.4 (Restated). Let a, 5 E (0,1), 6(X, Y) be a sufficient statistic for Š, such that Š is conditionally independent of X,Y given Φ. and W = (Eoeg :6 Bo E R G E g} Assume that the data {(X,, Y:) are drawn ii.d. from a distribution D, [Eijiett1 are drawn i..dd from a distribution Dm, independently from the dataset, and the distribution of 5 (X, v)
Y) is continuous. There exists absolute constant C' such that, with probability least 1 over the randomness of the calibration dataset {X,,, Yi) and the noise {E:Jie(n) the (randomized) prediction set C given by Algorithms and 2 satisfies, for all GE G.
PP [Yn41 E ((Xn+13en+1) Znt1 E G, (X,, YI, (.)))eee))) - -(1 -1-
g
9
2 1lm(4(///0)
C
max(u, (x, 1 atv
PlZn+1 G
17

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Condittonal Coverage
Proof. Since S is conditionally independent of X, Y given o, more formally Š TL X,Y e(X,)), and IL X, K,
we have S, e 11 X,Y ((, Therefore S 11 X,Y Y), This implies for any #1, M1, 22, 3/ such that 6( M1) = (z B2), we have S(x1, V1.E) = (z2, 82, Therefore, S(X,Y YY is measurable w.n.t o(X, Y), From the definition of W, any w(x,V Y) with w E W is also measurable w.r.t. d),,
According to Theorem 3.1, there exists an absolute constant C such that, with probability at least - 6 over the randomness in {(X,, Yi) be(n and (=))e()) for every ug W.
W X) ((xx, - [
Ex
c(X:E)) (1- a]]] (11-))]1
d +
d
+ max 10:.1-a01 1 12
||
CV n
n
9
9
maxfa, la 2 21 (1/0)
||
CV
+
n
n
For any G E G, by taking w - नददल PlZ E G ((X,)) = 0(z U)}, we have 11
Since
PlZ
S(X, Q(XY) are measurable w.r.t. o(X, E, by Bayes formula,
Ex
(xx(X (1
(1 [a)]]]===
Plz E ( (Xx (1(((x,),))(((x). -(1 -(1-a)]
Ex.Y,e
G[
PiZ E (( (1 (115 s s(xxr) (1 - a))]
E|
(5x( s ((x,)) - (1 (1 ( 2EG
E
E 1 5(xxt1, Y S ((x++1, (( - (1 - a) Zut1 E EG, (X,, Yohhee
P [Yn+ (C((n-1;e+41) Zn+1 E G, (X,, Y,, sikemm) - (1-a).
Combining the two equations above, the proof is complete.
Corollary 3.3 (Restated). Let parameters a, E (0, 1), and W - -GGe Bal((x, E G} : Bo E YR E G). Assume that the data {(X,, he) are drawn i.i.d. from distribution D. {E, (i(nnt] are drawn i..dd. from a distribution Dm, independently from the dataset, and the distribution of (X,Y,e) | ((x, Y) is continuous. There exists an absolute constant C' such that, with probability at least 6 over the randomness of the calibration dataset {(,,, Y.) ke) and the noise (ex [et)e the (randomized) prediction set C, given by Algorithms 1 and 2 satisfies, for all G 9.
IP E EC(X | (X Yn+1) 1) E G, (X,, Y,, Exemm - - -1-a)) a)) s
1
9
9 n + maxfa, 1 2 Inn (1(44(1//8)
C
P((Xn-1, Yn+1) G
n
7
Proof. Corollary 3.3 follows directly from Corollary 3.4.
Corollary 3.5 (Restated). Let a and 8 be parameters in (0, 1), and W = ( B E Rd) denote a class of linear weight functions over a bounded basis & X' y + nd Assume that the data {(X,, Yi) are drawn i.i.d. from distribution D, {e, )xj[++1] are drawn i.i.d. from a distribution Dm. independently from the dataset, and the distribution of
3 (,) (XX, Y) is continuous. Then, there exists an absolute constant C' such that, for every distribution D7 such that d7 dr dPp (x, 3) < B for any z X and y E V, with probability at least ô over the randomness of the calibration dataset (X,, Yi))ee()) and the noise (ex)se(n) the (randomized) prediction set C, given by Algorithms and 2,
d'rr E W and dPp
18

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditiona Coverage
satisfies
C + d n
2 ll((4/))
IP(Y++1 E ((Xntlien+)) (X,, Yi,ee) (1 a)] s B
max 1- ady
1
where (Xn+1; Ya+1) are drawn independently from the distribution Dr.
dP dr (x, v)
Proof. This corollary follows from Lemma A.1 for any weight function E W of the form w(x.v) = de
with
|oo]oo B.
A.2. Comparison with Previous Results
For weight functions defined only on the covariates, Kandinsky conformal prediction obtains the same type of guarantees studied in Jung et al. (2023); Gibbs et al. (2023); Areces et al. (2024). Jung et al. (2023) and Areces et al. (2024) essentially implement the same quantile regression method as that described in Algorithms and for the corresponding class of weight functions and for deterministic scores. Typically, for covariate-based weight functions the distribution of S(X,Y) (X)
is continuous and, hence, it is common to set S(z, y, a) = S(x, y). Jung et al. (2023) focus on the group-conditional case, where the groups are subsets of X. and their analysis of high-proe sigh-probability coverage less optimal compared to the result in Corollary 3.3. Additionally, our analysis of the expected weighted coverage deviation Corollary 3.2 provides tighter upper bound compared (Areces al., 2024). Lastly, Gibbs et al. (2023) implement a different quantile regression method that we discuss further in Section 4.
A.3. Computational Details
In Algorithm 2, the prediction C defined as the subset of all labels Y where the score below the value determined by the quantile function that varies with y. This makes calculating the prediction set from the quantile function q complex for large finite sets of labels, and more so for continuous label domains. This is problem that also be encountered in full conformal prediction. For several applications described in this section and for certain chosen score functions, there exist oracles that, given the quantile function q and the test point X return the prediction set C.
B. Proofs from Section
In this section, we provide the proof of Theorem 4.1.
Theorem 4.1 (Restated). Let a be a parameter in (0, 1), and let W = w= { 3 E Rd) denote a class of linear weight functions over a basis 4 X x y + Rd. Assume that the data {(X,, K)) are drawn i.dd. from a distribution D, {Ei ]ej[+1] are drawn i.i.d. from a distribution Dm, independently from the dataset, and the distribution of S (X,Y,e) (XX, Y) is continuous. Then, for any W, the prediction set given by Algorithm 3 satisfies
d EDi max |w (x YOI n [E|n+1]
w)]l S
where D is the calibration dataset ((X,,))) E is the corresponding noise (ealie()) and D4 is the full dataset ((X,, [e))e((++1)-
Proof. This proof follows the techniques developed (Gibbs et al., 2023). For simplicity, Š (X,, Y,, is denoted by S. Let TY.... be the quantile function Algorithm computes for the true label Y For fixed w W our objective can be reformulated as
Ep, a, w)] = E ( Yat1) (1 (Ya+1 E CC(X
a))]
E [ Yn+1) (a- (3at > @ra.. (Xo+1, Xn+1)
where the expectations on the right hand side are taken over the randomness of ((x,, Y:) (e)ee))) and (e)))))
19

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Connditonall Coverage
Since the data ((,,, Y)) bEj++1 are i.i.d., the random noise components (Eihe[n+1) also i.i.d., and based Algorithm 3, Tr is invariant to permutations of {(,, (e(n+1)) the triples in
[(w(X, (i),9r... 3x,
exchangeable. Hence, we have that
w (Xnn11 Yn+1) (a (a-1 [nt+
1 > 2Y.41 (Xn+1, Y2+2)
Ep,e/wCD(C, w)] = E
Σ w(X,, Yi) (a- {3, > @r (X.:
=
n +
#E|n+1]
Since TY is minimizer of the convex optimization problem defined in Algorithm 3, we have that for a fixed w E W, fixed datapoints ((X;, Y)) and fixed noise (e))=e]=+1]
e On n+1
Σ iE[++1]
(X + mo(x; x)).
1==
Computing this subrgradient, we obtain that
on
Σ
lalTv.., Vi) + (X,, Yi),
n + iE(n+1]
Σ w(Xi, Yi) (a-1 प.... (X,, xi)3) 115, + 1+)
n ++11
iE/++1]
Σ u.w X (X, x2)) 0: El 1
EE|--1]
Let of be one of the values in ja - 1, a] that set the subgradient to zero. Then, we have that
Σ
w/ (X Vi) (a 1(3,
(a-1(5: > Tr.. (X,, (X1,Y)))
iE[x+1]
1
Σ iE|N]
(a-v))(2
(5, Tr,.p (X,, Y.)).
Going back previous computation where we have only fixed W, apply the equality above obtain that
Ep,x(wCD(C,,, a, w)]
w/ ((,,, Vi) (a {3, Tr... (X (X., Yi)
12.
(E(++1]
Σ (a- (e-v,)((X,, YJ (X,,
[E[+11]
Now, we want to provide an upper bound for our objective. Recall that from the theorem formulation D4
20

---

Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conddttonal Coverage
((X, V)Je//+111 and let E+ (Es)NE/++1]- Since of 1, we get that
Ep,e (w,,[[CC(C,,,, = E
(a - (x), N (X1,
sE
<
E
i 1:) = qr., (X1,
7+1 1
max jE[n+1]
| (xxx
Σ
1(S; = @Y..i (X,,
n2 +
ic(x+11]
max |un(X,, Xi]l jE(n+I!
ED_
EE+
Σ
113, qY (X,, Ki) (o ())
n2
iE(++1]
=ED_.
(max
luo(X;; (2) je(n++]
1
EE+
Σ
1(5 = Tr. (X,, Yi) (0(X,, Ve)eet+11)
12
[E(++]]
We will now bound the inner expectation of the above expression by showing that conditioning on { Yi) [e))(())))
P
Σ
- -v. (I), d (0 Y.)
jE[++1]
In more detail, we can upper bound this probability follows
Σ 115 = TY... (X,, Y)) > (x(X,, Y.)een+t
EE(n+1]
31 Si <...
ja+t Sn 1 Wi (d + 11,3; = Tr. (X,, ()) 1)eemtta] s
Σ
Piie [d+ [d+ 11. q. (X,, ()) Y)) s
1sh S..Kias
Σ
Fie Vie [d+ 11,3; xX XX
Σ
PP
E Rd s.t. Vi dd+ 11, B& (X,, Yi) (0((X, Yi)
15h Ste
kE(4
Σ
( 3am) E RowSpace (+ Yn 10 Yunrs (X,, Y,) h))ee)+
15h Shat
We notice that R ( 1n (X
i Y ))+ is d-dimensional subspace of Rd+1 Since for fixed (X, Y.) [e))sen+t) the scores S,..... Sean are independent and continuously distributed, we have that for all <
ji ... Ja+1 I I1
P ....... s. jan))) E R ([D(X,,, K,)I. | Yyann 1)) (X Yi)eeet 0.
Combining the inequalities of the steps above, we have proven that for all E W
max ELDE (wCD(C, w)]l S n sE(n+1]
Ep_
[w[X,, Yi)l
21

---

Kandinsky Conformal Prediction: Beyond Class- and Lovariate-Condittona Coverage
C. Additional Experimental Details
We use Histogram-based Gradient Boosting Tree through the implementation of scikit-learn (Pedregosa et al., 201 I), Specifically, we use the HassGraiiennoostigguasiiieeeee train the basis weight functions for Kandinsky conformal prediction. We use HistCrafiennoootiiggggssss hyperparameters suggested by scikit-learn except that we max mae_ to 250.
train the base model for ACSIncome. We apply default
C.I. ACSIncome
We preprocess the dataset following Liu al. (2023). We additionally apply logarithmic transformation of labels with base 10 and scale the label to (0, 1] by min-max scaling.
We train the base Gradient Boosting Tree regressor on 31,000 samples with 10,000 from each state. The calibration set contains 4,000 samples per state and the test set contains 2,000 samples per state. Given a number of groups [g], we select samples from states with the [g] smallest indices. We train the basis Kandinsky's weight function class on the training set with selected states, but the base predictor not retrained. We also filter the calibration and test set for selected states. repeat the experiments 100 times by reshuffling the calibration and test set, but the training set is fixed such that Kandinsky's weight function class also fixed for a given number of selected states.
We take the deterministic score function of Conformalized Quantile Regression (CQR). Given base predictors fa/2(11) and f1 f1=)/((z) for the a/2 and ox/2 quantile, respectively,
S(x, v) = max - /1
v). 3 = S.
C.2. CivilComments
Following Koh et al. (2021), we split the dataset into 269,038 training samples and 178,962 samples for calibration and test. We finetune a SAABBERRT-ass-uncaa model with a classification head on the training set, following the configurations of Koh et al. (2021). We randomly redistribute samples between the calibration and test sets to vary the calibration sample sizes. Since the groups are overlapping, we estimate the ratio between the group average sample size and the overall sample number of 178,962. Then we downsample the dataset accordingly approximately reach prescribed group average sample size in the calibration set. We repeat the redistribution procedure 100 times, but the training set is fixed such that the DistilBert model is trained only once. However, we train the weight functions of Kandinsky conformal prediction on the calibration set, since we are considering the setup where training samples are only accessible to algorithms by the base predictor. Therefore, the weight function class is retrained for each calibration set. Since group sample sizes can be different between runs, in Figures 4(a) and 4(b), annotated group sample sizes are estimated by the mean of actual group sample sizes over 100 runs.
We take the randomized score function of Adaptive Prediction Sets (APS). Given the base classifier f(x) that outputs the probability vector for all classes, we sort their probabilities in decreasing order.
fay(2) 2 (z) ... (2)
We use (x) to represent the component of fxx) for the class y and (y) represent the order of (y( such that (z) = (z).. The non-conformity score is given by
h (x)-1 Σ
f(s(()) + (zf( Uniform(0, 1].
22


Reviews:
[{"review_id": "jIvjugoSn5", "reviewer": "Reviewer_oFZY", "summary": "This paper proposes a new conditional conformal prediction framework named **Kandinsky conformal prediction** , which considers the conditional coverage given the information from both covariate and label. The theoretical results also improved existing bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We would like to thank you for your feedback. We address your comments below.\n\n### 1. “Add explicit definition of C(X_{n+1}) in Algorithm 3.”\n\nThe definition of $C(X_{n+1})$ is given in the equation of the second line of Algorithm 3, where it includes all $y$ such that the score function on the test point is smaller than a threshold $\\hat q_y$. The threshold $\\hat q_y$ is defined in the next equation, which is computed by quantile regression on both calibration samples and test samples.\n\n### 2. “Provide examples or experiments for Fractional group memberships.”\n\nThe ACSIncome experiment in the paper is designed with fractional group memberships. The dataset is derived from US Census data collected from different states, which are considered as groups. The state attribute is omitted from the covariates and test point labels, leading to fractional group membership: as defined in L220, we consider fractional group membership with groups defined by unobserved attributes, such that the membership can only be inferred by a probabilistic function over $X$ and $Y$. Given the ground-truth group, the membership is always deterministic. But the membership is fractional for the predictor which observes $X$ but does not observe the group.\nWe propose another example in the introduction (L74). Due to regulatory restrictions, sensitive attributes are sometimes prevented from being used for prediction. Grouping by unobserved sensitive attributes causes fractional membership.\n\n### 3. “Discuss the technical reason for improving the convergence rate over Roth (2022); Jung et al. (2023), and the sharper dependence on $|G|$ compared with Areces et al. (2024).”\n\n**Compared to Roth (2022); Jung et al. (2023):** \n\nWe establish a connection between the ​subgradient of the empirical quantile loss and the ​empirical coverage guarantee, then prove concentration for the empirical coverage.\nRoth (2022) and Jung et al. (2023) connect the ​subgradient of the expected quantile loss to the ​expected coverage, so they must prove the concentration for the quantile loss itself. The empirical coverage yields tighter concentration because it is the sum of binary-valued functions. Roth (2022) and Jung et al. (2023) only prove concentration for a ​regularized quantile loss, and the regularization worsens sample complexity.\n\n**Compared to Areces et al. (2024):** \n\nAreces et al. (2024) prove uniform convergence of the weighted coverage for the whole function class, but we prove uniform convergence only for the basis weight functions since the function class is a vector space. This sharpens the dependence on |G|.\n\n### 4. “Lack of comparison results with Romano et al. (2020a).”\n\nRomano et al. (2020a) consider a different setting from ours. They assume that the group label for the test point is known, while we address the more general case where the group label is latent. Therefore, their method cannot be directly applied in our experiments.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I have checked the proofs in Section A.1, which are correct to me.", "experimental_designs_or_analyses": "Yes. The experiments are solid.", "relation_to_broader_scientific_literature": "The proposed method expands the scope of condition-conformal methods in Jung et al. (2023) and Gibbs et al. (2023).", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Weaknesses**\n\n1. The applications in Section 3 are not fully explored in experiments.\n\n2. Lack of comparison results with Romano et al. (2020a).", "other_comments_or_suggestions": "1. Add explicit definition of $C(X_{n+1})$ in Algorithm 3.\n\n2. Provide examples or experiments for Fractional group memberships.\n\n3. Discuss the technical reason for improving the convergence rate over  Roth (2022); Jung et al. (2023), and the sharper dependence on $|\\mathcal{G}|$ compared with Areces et al. (2024).", "questions_for_authors": "No.", "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": "", "extra_scores": {}}, {"review_id": "3NlMnf9A81", "reviewer": "Reviewer_QKpU", "summary": "The authors build on the rich literature on extensions of the conformal prediction framework, that traditionally yields intervals where marginal probabilistic calibration is true.\nMore specifically, they propose a method able to infuse very generic notions of group-conditional calibration, moving from previous work covering only more specific cases.\nSuch method, called Kandinsky Conformal Prediction, is thus proposed, described in detail and then tested on real world tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We would like to thank you for your valuable comments. We address your questions and concerns below.\n\n### 1. “It is unclear why the proposed method performs better…Kandinsky beats other methods.” “Your test examples seem to show… alternatives allround?”\n\nWe provide two concrete example scenarios where KCP's generality directly improves coverage:\n\n- **Overlapping Groups:** We consider overlapping subgroups jointly defined by covariates $X$ and labels $Y$. For example, in our experiments with the ACSIncome dataset (income prediction task), groups are naturally overlapping and jointly defined by subsets of demographic attributes and income levels. In such scenarios, standard Mondrian conformal prediction does not apply, as it requires disjoint groups. Furthermore, the conservative baseline method introduced by Barber et al. (2021)—which assigns the most conservative prediction sets to test points based on all overlapping groups to which they belong—tends to produce excessively large and thus impractical prediction sets. Our experiments also validate this result.\n\n\n- **Latent or Implicit Groups:** KCP effectively handles scenarios involving latent groups or implicit subpopulations defined by attributes unavailable at test time. Previous methods that rely exclusively on explicit group annotations are inadequate for such cases. For example, class-conditional conformal prediction uses only labels $Y$ as explicit group identifiers, making it insufficient for capturing latent groups. In contrast, the Kandinsky framework jointly leverages covariates $X$ and labels $Y$ to infer implicit, probabilistic group memberships. Our experiments with the CivilComments dataset precisely demonstrate this scenario: group annotations are unavailable at test time, and our results show that KCP successfully maintains the desired coverage guarantees, whereas baseline approaches like class-conditional CP fail to do so.\n\nAdditionally, we want to emphasize that KCP unifies existing methods (class-conditional, covariate-group-conditional, Mondrian) without increasing complication. It reduces general group-conditional coverage to a single quantile regression over an appropriately chosen function class. Our main contribution rigorously shows that this approach achieves stronger conditional coverage guarantees through a practical and simple algorithm.\n\n\n\n### 2. “I would be interested to know what degree of overlap between classes would make Kandinsky better than the alternative. “\nIn the CivilComments test dataset, the number of groups that a sample belongs to follows the distribution below:\n| Number of Groups | Samples |\n|-----------|---------------|\n| 0         | 81235         |\n| 1         | 37226         |\n| 2         | 12041         |\n| 3         | 2704          |\n| 4         | 470           |\n| 5         | 88            |\n| 6         | 13            |\n| 7         | 4             |\n| 8         | 1             |\n11% samples belong to at least two overlapping groups. Under such a degree of overlapping, Kandinsky achieves half the coverage deviation of the best alternative (the conservative conformal prediction method). \n\n\n### 3. Are there applicative situations where Kandinsky CP \"breaks down\"?\n\nWe conducted experiments to systematically analyze scenarios where Kandinsky Conformal Prediction (KCP) provides an advantage. Specifically, we explored the effects of varying two critical parameters: the number of groups and the sample size per group. In the ACSIncome dataset, we fixed the number of samples per group while progressively increasing the total number of groups. In the CivilComments dataset, we varied the total sample size while keeping the number of groups constant.\n\nOur results show that KCP scales robustly with an increasing number of groups, whereas baseline methods deteriorate significantly (Fig 1a). Additionally, KCP’s performance consistently improves with larger sample sizes. However, we observed a scenario where KCP underperforms compared to class-conditional conformal prediction when the sample size per group falls below approximately 250 in the CivilComments dataset (Fig 1d). This occurs because class-conditional prediction assumes binary groups defined solely by labels Y, giving it a larger \"effective\" sample size per group—up to eight times more than KCP, which handles 16 overlapping groups jointly defined by X and Y. Consequently, class-conditional prediction may initially appear competitive at small sample sizes, but its inherent limitations become clear as sample sizes grow. In summary, KCP demonstrates substantial practical advantages, particularly in settings with many groups and moderate to large sample sizes per group.", "claims_and_evidence": "From a theoretical perspective, Kandinsky CP is fully charachterised by an extensive theoretical analysis, with well proven results.\nI am a bit skeptical about the applicative case study, but more on it below.", "methods_and_evaluation_criteria": "The applicative benchmarks are well chosen and very representative (maybe a bit limited).", "theoretical_claims": "I have checked all the proofs in the manuscript, and they seem correct.", "experimental_designs_or_analyses": "While I find the theoretical endeavour of sure and clear merit, I remain a bit skeptical about the applicative case studies.\nTheir results show that Kandinsky CP gives better results than the methodologies already available in the literature.\nI believe the paper is lacking in this respect along two directions\n\n-It is unclear why the proposed method performs better, and thus when such an increase in complication is worth from an applicative perspective. \nThis can be achieved via a more extensive study on real world datasets, in order to charachterise the types of analytical scenarios where Kandinsky beats other methods\n-Along this same directions, it would be interesting to charachterise the performance of the method also via the use of synthetic datasets... e.g. I would be interesting to know what degree of overlap between classes would make Kandinsky better than the alternative.", "relation_to_broader_scientific_literature": "As stated previously, this result is generated in the context of the rich body of literature about non-marginal conformal prediction. The authors make a good effort at summarising the fundamental references.", "essential_references_not_discussed": "All the fundamental literature pieces are there, I would only cite the second edition of Algorithmic Learning in a Random World (same authors, but published in 2023)", "other_strengths_and_weaknesses": "none of relevance", "other_comments_or_suggestions": "none of relevance", "questions_for_authors": "Your test examples seem to show a supremacy of Kandinsky CP with respect to other methodologies. Do you have any idea why? Is it because of specific features of the dataset, or just because the method is better than the alternatives allround?\n\nAre there applicative situations where Kandinsky CP \"breaks down\"?\n\nThis can be explored also with synthetic datasets.", "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": "", "extra_scores": {}}, {"review_id": "2DkC9gg0Iy", "reviewer": "Reviewer_EL5A", "summary": "This paper is considering the problem of conformal prediction with conditional guarantees, particular allowing the conditioning event to be both a function of covariate X and label Y. They build upon the previously proposed technique in the literature which is based on training a linear quantile regression over the linear span of some predefined basis. This basis would then capture a finitely many conditioning events, which in this paper can be a function of X and Y. They prove both PAC-type and \"averaged over calibration\"-type coverage guarantees and have a number of experiments backing up their claims.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We would like to thank you for your review. We answer your question below.\n\n### 1. “... how should we design the basis (\\phi) in practice? … how do we systematically figure out what kind of conditioning event we have to include or more generally what kind of distribution shifts we have to consider … How can we design a meaningful basis as a function of X and Y?”\n\nThis is an interesting research direction. Towards this direction, we analyze theoretically and evaluate empirically the application of fractional group membership where we obtain the desired coverage for groups defined by unobserved attributes. For this application in Section 3.1 we define $\\Phi(X,Y)$ as the probability that the test point $(X,Y)$ belongs to a group $G$ based on the unobserved attributes conditioned on the value of $(X,Y)$. Our theoretical analysis is for the case where we know the true probabilities that define $\\Phi(Χ,Υ)$. In practice, we can use the calibration data that includes the value of the protected attribute to estimate the probabilities for the basis $\\Phi$. We implement this approach in our experiments in Section 5.", "claims_and_evidence": "I believe all the claims in the paper are accurate. They accompany their propose method with a number of special cases that makes everything crystal clear.", "methods_and_evaluation_criteria": "The evaluation methods make sense to me.", "theoretical_claims": "All the theoretical claims make sense. I have looked through their proofs, the proofs are very similar to the work of [Gibbs et al 2024], which is based on analyzing the sub gradients of the quantile regression. The resemblance is natural as they are generalizing their method. That being said, it might be the case that I have missed some small errors, as I did not check all the equations one by one.", "experimental_designs_or_analyses": "They make sense to me.", "relation_to_broader_scientific_literature": "They broaden the use case of conformal prediction in the scenarios where conditional coverage is important. The extra dependance on Y makes this framework more flexible from the application point of view as it can model more advanced subpopulations of the data or more advanced distribution shifts (beyond covariate shift).", "essential_references_not_discussed": "Not that I know of.", "other_strengths_and_weaknesses": "look at questions ...", "other_comments_or_suggestions": "look at questions ...", "questions_for_authors": "Even though the extra dependance on Y in designing the conditioning event makes the framework more flexible, however it highlights the question of how should we design the basis (\\phi) in practice? This problem also applies to the works of [Gibbs et al] and [Jung et al] on covariate conditional events. Of course in some case we can design the groups relying on domain knowledge of fairness considerations and so on. But more generally, the question is how do we systematically figure out what kind of conditioning event we have to include or more generally what kind of distribution shifts we have to consider. Now for the case of covariate shifts, there is this option of taking advantage of unlabeled data from the test domain, which might be accessible in some scenarios. But unlabeled data would not be useful to figure out a good basis function beyond covariate shifts. So how can we design a meaningful basis as a function of X and Y? \nIn thinking about these it might also be good to take a look at some other research directions like [1] which are thinking about this question in the setting of covariate shift, but might give some ideas for the more general case in this paper.\n\n[1] conformal prediction with learned features", "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": "", "extra_scores": {}}, {"review_id": "L19rYDHmCf", "reviewer": "Reviewer_mj6f", "summary": "The paper proposes an extension of the conditional coverage works of Jung et al. and Gibbs et al. to functions of covariates and labels, not just covariates as in these previous works. Experiments on ACSIncome and CivilComments datasets are included.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your constructive feedback. We address your concerns below.\n\n### 1. “The paper provides the same flavor of bounds as GCC'24, but for weight functions that depend on both X and Y. Some initial work in this direction was completed by Blot et al (https://arxiv.org/abs/2406.17819), but this paper takes it yet another step further by proving a larger set of results including two-sided bounds.”\n\nThank you for pointing us to the paper by Blot et al. In our paper, we provide results that are stronger than Blot et al. in two ways. First, Algorithm 3 and the bound in Theorem 4.1 in our paper have a similar flavor to the results in Section 2.2 of Blot et al. However, their result is a one-sided bound, whereas we derive a two-sided bound assuming that the data are i.i.d. and that the distribution of $S(X,Y)|\\Phi(X,Y)$ is continuous. Second, in Section 3 we obtain high probability bounds (that are in general stronger than expectation bounds) using Algorithms 1 and 2, under the same assumptions. We will incorporate this citation and discussion into our paper.\n\n### 2. All the arguments in GCC'24 already hold for randomized score functions. There is no novelty in using a randomized score in the quantile regression.\n\nThe use of randomized score functions is not the key contribution of our work. The main reasons why randomized score functions are used in Gibbs et al. (2023) and our paper though are somewhat different. In Gibbs et al. (2023) the authors use randomized score functions to obtain exact coverage. The difficulty when extending quantile regression to work for weight functions of the form $w(X,Y)$ is that conditioning on $X$ and $Y$, the value of a deterministic score function $S$ is fully defined (as opposed to the setting in Gibbs et al. (2023)). Therefore, we add randomization to the score function as one of the ways to overcome the obstacle of $S(X,Y)|X,Y$ not being continuous for a deterministic $S$. \n\n### 3. Unclear what randomness wCD is integrating over. if C is an argument, then it can be randomized (as in the case of a random score). Then in what sense does the inequality in Theorem 3.1 hold? Almost surely?\n\nIn Section 2 we define wCD as an expectation over the test point $(X,Y)$ and the internal randomness of $\\mathcal{C}$ (which exists when as you mention we use a randomized score of the test point). Since wCD is by definition integrating over the randomness of $\\mathcal{C}$, in Theorem 3.1 the dependence on the randomness of the score of the test point is accounted for in wCD. To explain things further, the guarantee in Theorem 3.1 holds with high probability over the randomness of the calibration dataset and the noise $\\{\\varepsilon_i\\}_{i\\in [n]}$ that is used to randomize the scores of the calibration data points.", "claims_and_evidence": "Claims are supported by the evidence in the paper.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not carefully check the proofs.", "experimental_designs_or_analyses": "Although the analysis looks correct, there is no code available to double check.", "relation_to_broader_scientific_literature": "Extending the results of GCC'24 to test-label conditional coverage guarantees.", "essential_references_not_discussed": "See Blot et al. https://arxiv.org/abs/2406.17819 for an extension of the GCC paper to also include weight functions that depend on the label as well as the covariate. The algorithm in Section 4 should be subsumed by this paper, although the two-sided bound is new.", "other_strengths_and_weaknesses": "The paper provides the same flavor of bounds as GCC'24, but for weight functions that depend on both X and Y. Some initial work in this direction was completed by Blot et al (https://arxiv.org/abs/2406.17819), but this paper takes it yet another step further by proving a larger set of results including two-sided bounds.\n\nIt is a reasonable contribution to the field to extend the GCC'24 analysis to these , although it seems to include no highly novel technical devices. The experiments are reasonable for the purpose of demonstrating validity of these results, although not extraordinary.", "other_comments_or_suggestions": "All the arguments in GCC'24 already hold for randomized score functions. There is no novelty in using a randomized score in the quantile regression.", "questions_for_authors": "Unclear what randomness wCD is integrating over. if C is an argument, then it can be randomized (as in the case of a random score). Then in what sense does the inequality in Theorem 3.1 hold? Almost surely?", "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": "", "extra_scores": {}}, {"review_id": "NOqIbDiKer", "reviewer": "Reviewer_1N7z", "summary": "The paper proposes Kandinsky Conformal Prediction method for general group-conditional guarantees in contrast to Mondrian conformal prediction that ensures conditional coverage over a disjoint set of groups. Their framework handles overlapping and fractional group memberships, and allows for group memberships to be jointly defined by covariates and labels. They show this method is computationally efficient as it requires solving a single quantile regression over the vector space spanned by group functions; and statistically optimal as it matches the minimax-optimal conditional coverage error rate with finite samples. Through empirical evaluation on ACSIncome and CivilComments datasets, authors demonstrate their method achieves the best conditional coverage as measured by best group average coverage deviation and stable average coverage deviation with the increase in number of groups.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We would like to thank you for your review. We address your question and your comment below.\n\n### 1. I would like to see more details regarding the implementation of the algorithm (e.g., expanding section A.3), especially as the code was not shared in the current submission.\n\nThis links to the code: https://doi.org/10.5281/zenodo.15104271. We will include the code in the publication and we are ready to share further implementation details.\n\n### 2. Is there any reason why comparison with Gibbs et al., 2023 and Ding et al., 2023 (class conditional conformal prediction) is not included in the experiments? I believe this would help understand the performance improvements offered by the proposed method in the very specific cases introduced in the paper.\n\nWe have compared Kandinsky conformal prediction with class conditional conformal prediction with the CivilComments dataset. However, the class conditional method is not implementable for the regression task in ACSIncome. The method of Gibbs et al., 2023 does not scale for the image tasks we consider because it trains the image classifier from scratch to learn the weight functions. This violates the post-hoc nature of conformal prediction. Kandinsky trains the group classifier using the two-dimensional input of logits and labels, which is scalable.", "claims_and_evidence": "The claims made in the submission regarding their general formulation of conditional coverage are supported by their theory (Theorem 3.1, Corollary 3.4) and accompanying proofs. The experiments empirically validate these claims.", "methods_and_evaluation_criteria": "Yes, the proposed method provides a general framework for conditional conformal prediction, where the weight function class can be adapted to obtain group-conditional guarantees, Mondrian conformal prediction, conformal prediction with fractional group membership, and distribution shifts. The evaluation metric of group average coverage deviation also makes sense.", "theoretical_claims": "I went over the proofs for Theorem 3.1 and Corollary 3.4 in the Appendix.", "experimental_designs_or_analyses": "I checked the experimental analysis for both ACSIncome and CivilComments datasets. I do not see any issues with the current design choices, but there is definitely scope to make the empirical evaluation more extensive (in terms of datasets, score functions, as well as choice of the function class).", "relation_to_broader_scientific_literature": "This paper expands the existing conditional coverage guarantees to allow overlapping groups and fractional memberships that are defined over both covariates and labels. As the paper mentions, when weight functions are based on covariates, the method provides the same type of guarantees as in past work but with tighter bounds on expected weighted coverage deviation.", "essential_references_not_discussed": "I feel the paper is fairly complete in its discussion of important references for understanding the context.", "other_strengths_and_weaknesses": "I appreciate the general framework proposed and the flexibility it offers to obtain the desired coverage guarantees for several applications. I also found the paper to be well-written and the proofs very detailed.\n\nRefer to questions below for specific concerns regarding empirical evaluation.", "other_comments_or_suggestions": "I would like to see more details regarding the implementation of the algorithm (e.g., expanding section A.3), especially as the code was not shared in the current submission.", "questions_for_authors": "Is there any reason why comparison with Gibbs et al., 2023 and Ding et al., 2023 (class conditional conformal prediction) is not included in the experiments? I believe this would help understand the performance improvements offered by the proposed method in the very specific cases introduced in the paper.", "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": "", "extra_scores": {}}, {"review_id": "JsLBQtssRq", "reviewer": "Reviewer_mFd6", "summary": "The present paper introduces an approach to weighted conformal prediction that employs quantile regression as a solution. The authors study general weights depending both on covariates and labels and provide theoretical guarantees via high probability upper bounds. Several particular examples of weighting functions are considered as corollaries of general results. Online setup is also considered separately. Some numerical illustrations are provided.\n\n## Update after rebuttal\n\nI appreciate the review by authors. I think that the paper is generally sound and, while not having a single big contribution, improves the existing results in mainly generality of approach and sharpness of theory. I was slightly confused by the rebuttal by authors where at several places they were overclaiming the contributions (which is actually much less present in the paper itself). In particular, there is no new algorithm in the paper (adding Y as input doesn't lead to new algorithm). I increase my score by 1 point to acknowledge my general positive impression about the paper. However, I recommend the authors to further improve the clarity of the paper. For example, the introduction of randomized score is not adequately done in the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank you for your review. Below, we address your questions:\n\n**Q1**. Most conformal prediction algorithms share a common structure, involving quantile regression followed by constructing prediction sets via comparison with a quantile threshold. However, significant differences emerge in the precise choice of the quantile function class and the selection of samples used for regression—these subtle yet critical choices underpin our algorithmic contributions.\n\n*Weight functions jointly dependent on covariates and labels*: Although inspired by Gibbs et al. (2023), we generalize their linear quantile regression approach from weight functions defined solely on covariates to those defined jointly on covariates and labels. This generalization is key to achieving broader and practically relevant coverage guarantees (e.g., overlapping and latent groups).\n\n*Efficient quantile regression without monotonicity assumptions*: While our Alg. 3 directly extends Gibbs et al. (2023), ensuring computational efficiency is non-trivial due to the loss of monotonicity structure utilized in their method. This monotonicity structure no longer holds when we consider groups jointly defined by $X$ and $Y$. To address this, our main method, Alg. 1, extends the computationally efficient quantile regression technique from Jung et al. (2023)—originally limited to covariate-conditional guarantees—to handle weighted coverage guarantees. This algorithm avoids the need to solve a quantile regression problem for all candidates y at test time.\n\n*Generalization of Mondrian prediction sets*: Alg. 2 further adapts the classic Mondrian conformal prediction approach to our generalized weighted setting.\n\n**Q2**. The primary challenge arises because both the conformity score and the quantile $\\hat{q}$ depend on both $X$ and $Y$. For example, in the analysis of quantile regression we want to bound the number of calibration samples $(X_i, Y_i)$ for which the score equals the quantile. In general, when this number is small, you can get a more accurate quantile estimator. As in prior work, we do this by conditioning on the random variables that fix the quantile’s value. However, in our case, if the score function is deterministic, then fixing the values of $X$ and $Y$ fully determines the score (as opposed to Gibbs et al. (2023) where they only need to condition on $X$). To address this, we show that it suffices to condition on $\\Phi (Χ, Y)$, which preserves uncertainty in the score. For non-continuous $S|\\Phi$, we can consider any randomized score function $\\tilde{S}$ that satisfies the continuity assumption. \n\nAnother challenge arises when given a quantile function $\\hat{q}$ and the features of a test point $X$, we want to compute the prediction set. The issue is that both the score function and the quantile depend on the value of $X$ and $y$. Inspired by Mondrian conformal prediction, we obtain the prediction sets by returning all the labels y where the score $S(X,y) \\leq \\hat{q}(X,y)$.\n\n**Q3**. Areces et al. (2024) prove uniform convergence of the weighted coverage for the entire function class. We sharpen the dependence on $d$ by focusing on the basis weight functions, since the function class is a vector space.\n\n**Q4**. The alternative test-time algorithm in Sec. 4 achieves a different type of coverage guarantee based on exchangeability arguments. Specifically, this guarantee incorporates randomness over both the calibration dataset and the test point. In contrast, Alg. 1 and 2 provide a training-conditional guarantee, conditioning only on the fixed realization of the calibration data. Although these two types of guarantees are not directly comparable, exchangeability-based guarantees generally yield smaller coverage error bounds, as in our results in Sec. 4.\n\n**“the paper [1] considers … weight function.”**\n\nThank you for bringing [1] to our attention. Both this paper and ours address potential distribution shifts between the calibration and the test data, where the distribution over the features and the label changes. The main difference between the two papers is that we get coverage guarantees for a class of distribution shifts, while they consider a single distribution shift that they can estimate using samples from the test distribution.\n\n**“particularly odd issues … discussion of the score function.”**\n\nIn Sec. 3 we mention that “As is common in conformal prediction, our method ensures the desirable coverage for any score function $S$ [that satisfies the continuity assumption]”. For deterministic scores violating the continuity assumption, we mention that “we allow for the use of a randomized score function to break potential ties in quantile regression while keeping the assumptions about distribution $D$ minimal”. In our experiments we use the deterministic Conformalized Quantile Regression score function (Romano et al., 2019), and the randomized Adaptive Prediction Sets (APS) score function (Romano et al., 2019; Ding et al.,2023).", "claims_and_evidence": "There are 3 main claims in the paper:\n1. First study of the general formulation of the (group) weighted conformal prediction which considers weights depending both on labels and covariates.\n\nWhile, to the best of my understanding, previous work indeed didn't consider the weights dependent on labels in the context of group-conditional coverage, it is not clear whether this significantly changes the methods and and the theoretical analysis. Thus, I currently don't see whether this claim, while being formally correct, represents a substantial novelty with respect to existing literature.\n\n2. Introduction of the new method for conformal inference. \n\nThe introduced method coincides with already existing methods except for using labels as input variables for quantile regression. I don't think that calling the method a new one is warranted.\n\n3. Experimental evaluation of the proposed method\n\nThe experimental evaluation is very lightweight with just two datasets considered. For more theoretical paper, I don't necessarily see it as a drawback but also don't think that this part of the paper represents a strong contribution.", "methods_and_evaluation_criteria": "The methodological part of the paper looks correct.", "theoretical_claims": "I didn't check the proofs line by line but the results well correspond to the existing literature and look sound. I guess an improvement of $d^{1/2}$ in one of the bounds is due to explicit consideration of finite dimensional weight function (as opposed to the general VC class) but I might be wrong.", "experimental_designs_or_analyses": "I think that the experiments are generally sound though only two datasets are considered. I am somewhat confused with the choice of baselines as I don't see which of the methods uses only covariates for quantile regression (without using the labels).", "relation_to_broader_scientific_literature": "I think that the paper generally well relates to the existing literature mentioning the majority the relevant papers. However, the corresponding discussion is not complete as the authors do not elaborate on why and how the paper succeeds to generalize the previous works. More precisely, it is not clear why considering $w(X, Y)$ is more challenging than considering just $w(X)$.", "essential_references_not_discussed": "The authors generally relate the paper well to the existing literature on conformal prediction with distribution shifts. However, they claim that weights depending both on X and Y were not considered in the literature. However, it is not correct as the paper [1] considers general weights. Also, that paper performs the analysis generally similar to the one performed in the present paper except that it does not consider a VC class for the weight function.\n\n[1] Plassier, Vincent, et al. \"Efficient conformal prediction under data heterogeneity.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.", "other_strengths_and_weaknesses": "I generally keep up with the literature in this area though I was not aware of the couple of recent (2024) papers on the topic that are referenced by authors.", "other_comments_or_suggestions": "I think that the additional major issue with the paper is writing which is while being generally clear, fails to deliver by what means the paper achieves the results that are claimed. It includes the explanation of algorithmic and theoretical advances which are not properly explained (or their novelty is not explained to be precise). One of the particularly odd issues with writing is absence of any discussion of the score function. In particular, the authors introduce randomized score function $\\tilde{S}$ but failed to find in the paper any discussion of this function or example. As one more example, Section 4 introduces test-time algorithm and discusses its drawbacks (computational complexity). However, it doesn't discuss any benefits of this procedure which makes the reader confused.", "questions_for_authors": "1. What are the algorithmic innovations of the paper (if any)?\n\n2. What are the difficulties in theoretical analysis (if any) which one needs to overcome considering $w(X, Y)$ compared to simpler case of $w(X)$?\n\n3. Why you obtain the rate which us better by $d^{1/2}$ than previous works?\n\n4. What are the benefits of considering test-time algorithm?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces Kandinsky Conformal Prediction (KCP), a novel framework for conformal prediction that extends conditional coverage guarantees to weight functions dependent on both covariates (X) and labels (Y). Six reviewers evaluated the submission, assigning overall recommendations of three Accept (score: 4) and three Weak Accept (score: 3). All reviewers commend the theoretical rigor and the paper’s contribution to generalizing conditional conformal prediction. During rebuttal, the reviewers' concerns are mainly on the limited empirical evaluation and clarity of the writing. The authors’ rebuttal adequately addresses most concerns, and the suggested improvements can be incorporated in the final version to strengthen the presentation. The consensus leans toward acceptance, with scores reflecting confidence in the work’s value to the conformal prediction community.
Decision: Accept (poster)