Class-Conditional Conformal Prediction with Many Classes

1 Introduction

• 89.8% marginal coverage on ImageNet concealed class-specific results: water jug coverage was 50.8%, while flamingo coverage was 99.2%.STANDARD was run at a nominal coverage level of 90% on 50,000 randomly sampled examples.Source: §1 · p. 2
• Clustered conformal groups classes with similar score distributions and combines their calibration data, often improving class-conditional coverage over STANDARD and CLASSWISE when calibration data per class is limited.The evaluation covers four large-scale classification data sets, each with 100 to 1000 classes.Source: §1 · pp. 2–3, Figure 1 · p. 2

1.1 Related work

• Previous studies examined binary, 3-way, 4-way, or 10-way classification and outlier detection, generally where data was abundant relative to classes; this work targets class-conditional coverage in many-class, limited-data settings.Source: §1.1 · p. 3
• This paper targets class-conditional coverage rather than X-conditional coverage, which is impossible for every input without further assumptions and can be less interpretable when labels are deterministic given inputs (Vovk, 2012).Prior work has pursued approximate X-conditional coverage through score functions or modified conformal procedures (Romano et al., 2019, 2020b; Angelopoulos et al., 2022; Romano et al., 2020a; Guan, 2023; Gibbs et al., 2023).Source: §1.1 · p. 3

1.2 Preliminaries

• STANDARD uses all calibration data for one stable threshold but lacks class-conditional guarantees; CLASSWISE guarantees them with per-class thresholds, which can be noisy and produce large sets.When a class has fewer than (1/α) − 1 calibration examples, CLASSWISE's threshold is infinite, so that class is always included in prediction sets.Source: §1.2 · p. 4

2.1 Meta-algorithm

• The method splits calibration data for clustering and quantile estimation, then pools scores within each cluster to estimate its quantile.Classes with insufficient clustering data are assigned to a null cluster and use the quantile from STANDARD calibration.Source: §2.1 · p. 5
• Clustered prediction sets achieve at least 1 − α coverage within every non-null cluster under the method’s stated guarantee.The guarantee follows from exchangeability between a test point and calibration points in its cluster when points are sampled i.i.d. from the same distribution.Source: §2.1 · p. 5
• With an oracle clustering whose classes have exchangeable scores within each cluster, CLUSTERED achieves class-conditional coverage for every non-null class.The paper notes that this condition holds, for example, when classes in a cluster have the same score distribution.Source: §2.1 · pp. 5–6

2.2 Quantile-based clustering

• Quantile-based clustering embeds each class with empirical score quantiles, then clusters the embeddings to group classes with similar score distributions.Classes with fewer than n_α clustering examples are assigned to null; the procedure uses weighted k-means, with class weights proportional to the square root of their example counts.Source: §2.2 · p. 6
• When within-cluster score distributions are sufficiently similar in Kolmogorov–Smirnov distance, the paper gives an approximate class-conditional coverage guarantee for non-null classes.The stated condition bounds the KS distance between every pair of classes in the same cluster by ϵ.Source: §2.2 · p. 6

3.1 Experimental setup

• Experiments use ImageNet, CIFAR-100, Places365, and iNaturalist with softmax, APS, and RAPS scores, targeting 90% coverage by setting α = 0.1.The first three datasets have roughly balanced classes, while iNaturalist has high class imbalance.Source: §3.1 · p. 7

3.2 Evaluation metrics

• CovGap measures the class-conditional coverage deviation from the target 1 − α across classes; AvgSize measures prediction-set sharpness, for which smaller is preferred at a fixed CovGap.The evaluation uses validation data separate from fine-tuning and calibration data.Source: §3.2 · pp. 7–8

3.3 Results

• STANDARD CovGap changes little with n_avg, whereas CLASSWISE CovGap decreases as n_avg increases because classwise quantiles are volatile with few examples per class.CLUSTERED is best or comparable across settings.Source: §3.3 · p. 8
• For softmax, CLUSTERED outperforms STANDARD and beats CLASSWISE below n_avg thresholds of 75 for ImageNet and Places365, 150 for CIFAR-100, and 50 for iNaturalist.For APS, CLUSTERED similarly beats CLASSWISE at sufficiently small n_avg, while STANDARD is comparable to CLUSTERED and only slightly worse at large n_avg; RAPS behaves similarly to APS with slightly higher CovGap.Source: §3.3 · pp. 8–9
• CLUSTERED achieves the best or near-best CovGap across experimental combinations, with particularly notable improvement over baselines at n_avg = 20 or 50.The comparison covers four datasets and multiple score functions; Figure 2 reports CovGap for softmax and APS, while RAPS results are deferred to Appendix C.1.Source: §3.3 · pp. 8–9, Figure 2 · p. 8
• STANDARD and CLUSTERED AvgSize remain relatively stable as n_avg changes, with CLUSTERED generally slightly larger; CLASSWISE set sizes decrease but remain especially large for iNaturalist.CLUSTERED achieves best or near-best CovGap in the reported CovGap–AvgSize tradeoff comparisons.Source: §3.3 · p. 9
• Auxiliary randomization generally improves CLASSWISE CovGap but changes STANDARD and CLUSTERED little; randomized CLASSWISE sets remain too large for practical use.CovGap tends to behave similarly to the fraction of classes undercovered by at least 10 percentage points.Source: §3.3 · p. 9

Extremely low-data regime

• When most classes have less than 10 calibration examples, STANDARD is the only option unless α is large; RAPS tends to improve class-conditional coverage, while softmax tends to produce smaller sets.The discussion says there is not enough data to run CLUSTERED or CLASSWISE in this regime.Source: §4 · p. 9

Low-data regime

• With around 20 to 75 examples per class, CLUSTERED often balances variance and granularity, achieving good class-conditional coverage and reasonably sized sets with softmax or RAPS.STANDARD with RAPS is also competitive toward the lower-data end of this regime.Source: §4 · p. 9

High-data regime

• Above 75 examples per class, CLUSTERED can perform well with softmax or RAPS, while CLASSWISE can also do well with balanced classes; with high imbalance, CLASSWISE is unstable for rare classes and produces excessively large sets.CLUSTERED is more robust under high imbalance because it shares data across classes.Source: §4 · p. 9

Extremely high-data regime

• When the rarest class has at least 100 calibration examples, CLASSWISE with softmax or RAPS is a good choice regardless of class imbalance.Source: §4 · p. 9

Regime boundaries

• The regime boundaries are experiment-dependent: the low-to-high transition occurs around 20-40 examples per class for softmax and 50-100 for RAPS, motivating CLUSTERED’s performance across regimes.The discussion cautions that boundaries depend on data characteristics and are not universal.Source: §4 · p. 9

Future work

• Future work could extend the approach to group-conditional coverage beyond class labels, including groups defined by input features or mixture-distribution components.Source: §4 · pp. 9–10

A Proofs

• For a test label in a cluster, its score and the independent proper-calibration scores in that cluster share a distribution, enabling the standard conformal coverage guarantee.The proof cites Vovk et al. (2005) or Lei et al. (2018) for that guarantee.Source: A Proofs · p. 13
• Proposition 2 follows directly from exchangeability and Proposition 1.Source: A Proofs · p. 13
• Within a cluster, the score distribution is a mixture of class-conditional distributions, and the bounded pairwise KS distance supports the proof’s triangle-inequality argument.The proof conditions on the clustering and proper calibration sets before analyzing the test point.Source: A Proofs · p. 13
• The class-specific coverage argument rewrites the event that the true label is included as a score-threshold event, then combines it with Proposition 1.The rewrite uses that CLUSTERED includes the true label when its score is at most the cluster threshold.Source: A Proofs · p. 13

B.1 Score functions

• The experiments compare three score functions: softmax, APS, and RAPS.Source: §B.1 · p. 13
• The softmax score uses the classifier’s softmax output for the input and label.The passage identifies f_y(x) as the softmax-vector entry for label y.Source: §B.1 · p. 13
• APS is designed to improve X-conditional coverage compared with the traditional softmax score, according to Romano et al. (2020b).Source: §B.1 · p. 13
• APS uses the sorted classifier softmax outputs and adds a uniform random term over the probability interval for the labeled class, according to Romano et al. (2020b).Source: §B.1 · p. 13
• RAPS modifies APS with a regularization term intended to reduce prediction-set sizes, which can often be very large with APS, according to Angelopoulos et al. (2021).Source: §B.1 · p. 14
• RAPS uses λ = 0.01 and kreg = 5 in all experiments; Angelopoulos et al. (2021) found these parameters worked well for ImageNet.Source: §B.1 · p. 14

B.2 Model training

• At least 250 examples per class are reserved from fine-tuning and calibration for validation of coverage and set size.Source: §B.2 · p. 14
• For non-ImageNet data sets, the base classifier is a ResNet-50 initialized with PyTorch IMAGENET1K_V2 weights and fine-tuned on each data set.Source: §B.2 · p. 14
• For ImageNet, a SimCLR-v2 model (Chen et al., 2020) extracts 6144-length features; a linear head trained on 10% for 10 epochs reaches 78% validation accuracy, and scores are obtained for the remaining 90%.Source: §B.2 · p. 14
• For CIFAR-100, 50% of its 600 images per class are used for fine-tuning; training for 30 epochs yields 60% validation accuracy.Source: §B.2 · p. 14
• For Places365, 90% of its more than 10 million images across 365 classes are used for fine-tuning; one epoch yields 52% validation accuracy.Source: §B.2 · p. 14
• For iNaturalist, experiments use family-level labels (1103 classes), fine-tune on 50% of the data, and reach 69% validation accuracy after one epoch.Source: §B.2 · p. 14
• Because imbalance and sampling leave some classes with too few validation examples, classes below 250 are removed, leaving 633 classes, and rare-class softmax entries are removed before renormalization.Source: §B.2 · p. 14

B.3 Measuring class balance in Table 1

• Table 1’s class-balance metric divides the example count in the rarest 5% of classes by the count expected under a uniform distribution; lower values indicate greater imbalance.Source: §B.3 · p. 15

B.4 Choosing clustering parameters

• The first heuristic requires at least twice as many clustering examples per class as clusters, while the second targets at least 150 examples per cluster on average.The second heuristic concerns proper calibration examples for the rarest class not assigned to the null cluster.Source: §B.4 · p. 15
• CLUSTERED is not particularly sensitive to γ and M: at n_avg=10 the heuristic selects γ=0.89, M=4, and at n_avg=50 selects γ∈[0.88, 0.92], M∈[7, 12].The heuristics do not always select values yielding the lowest CovGap; optimal settings depend on data set characteristics and score function.Source: §B.4 · p. 15

• Shaded regions in the additional experimental plots denote ±1.96 times the standard errors.Source: C Additional experimental results · p. 15

C.1 RAPS CovGap results

• Figure 4 reports CovGap across all datasets when RAPS is used as the score function.Source: §C.1 · p. 15

C.2 Additional metrics

• RAPS sharply reduces AvgSize relative to APS on ImageNet and slightly reduces it on the other three data sets.The RAPS hyperparameters were tuned on ImageNet; the paper notes that tuning them separately for each data set could likely improve set sizes elsewhere.Source: §C.2 · p. 16, Figure 5 · p. 17
• FracUnderCov counts classes with empirical class-conditional coverage more than 10% below the desired level; its trends generally mirror CovGap but are noisier, with large error bars.The plots cover all experimental settings.Source: §C.2 · pp. 16–17
• FracUnderCov cannot penalize uninformatively large sets: CLASSWISE has very low FracUnderCov on iNaturalist for every score function, despite producing extremely large prediction sets.CovGap can partly penalize this behavior because unnecessarily large sets often cause overcoverage, which CovGap penalizes.Source: §C.2 · p. 17, Figure 5 · p. 17

C.3 Auxiliary randomization

• The main-paper methods produce deterministic sets targeting at least 1 −α marginal, class-conditional, or cluster-conditional coverage, while randomization offers exact coverage if nondeterminism is acceptable.The passage notes that randomized sets may be undesirable in practice because predictions for the same input can vary with the random seed.Source: §C.3 · pp. 17–18
• An independent Bernoulli choice between quantiles that overshoot and undershoot the target yields exact 1 −α marginal coverage, and the same approach extends to CLASSWISE and CLUSTERED.The unrandomized quantile gives at least 1 −α coverage, while the alternative with an adjusted numerator gives less than 1 −α coverage.Source: §C.3 · p. 19
• Randomization leaves STANDARD and CLUSTERED essentially unchanged across CovGap, AvgSize, and FracUnderCov, while CLASSWISE improves CovGap and AvgSize but remains too large for practical use.The comparisons cover ImageNet, CIFAR-100, Places365, and iNaturalist, using softmax, APS, and RAPS scores as calibration examples per class vary.Source: §C.3 · p. 19, Figure 7 · p. 20, Figure 8 · p. 21