Parametric Scaling Law of Tuning Bias in Conformal Prediction
Authors: Hao Zeng
Kangdao Liu
Bingyi Jing
Hongxin Wei
Venue: ICML 2025 poster (2025)
Keywords: uncertainty quantification
conformal prediction
Primary area: general_machine_learning

Abstract: Conformal prediction is a popular framework of uncertainty quantification that constructs prediction sets with coverage guarantees. To uphold the exchangeability assumption, many conformal prediction methods necessitate an additional hold-out set for parameter tuning. Yet, the impact of violating this principle on coverage remains underexplored, making it ambiguous in practical applications. In this work, we empirically find that the tuning bias - the coverage gap introduced by leveraging the same dataset for tuning and calibration, is negligible for simple parameter tuning in many conformal prediction methods. In particular, we observe the scaling law of the tuning bias: this bias increases with parameter space complexity and decreases with calibration set size. Formally, we establish a theoretical framework to quantify the tuning bias and provide rigorous proof for the scaling law of the tuning bias by deriving its upper bound. In the end, we discuss how to reduce the tuning bias, guided by the theories we developed.

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Hao Zeng" Kangdao Liu" 12 Bingyi Jing' Hongxin Wei!
Abstract
due to the inherent characteristics of the data its usage in practice, such as time series analysis, domain shifts, and parameter tuning (Barber et al., 2023; Oliveira et al., 2024). Therefore, it is essential to understand and quantify the cov- erage gap that arises from the violation of exchangeability.
Conformal prediction is a popular framework of uncertainty quantification that constructs predic- tion sets with coverage guarantees. To uphold the exchangeability assumption, many conformal prediction methods necessitate an additional hold- out set for parameter tuning. Yet, the impact of violating this principle on coverage remains un- derexplored, making it ambiguous practical ap- plications. In this work, we empirically find that the tuning bias the coverage gap introduced by leveraging the same dataset for tuning and calibra- tion, is negligible for simple parameter tuning in many conformal prediction methods. In particular, we observe the scaling law of the tuning bias: this bias increases with parameter space complexity and decreases with calibration set size. Formally, we establish theoretical framework to quantify the tuning bias and provide rigorous proof for the scaling law of the tuning bias by deriving its upper bound. In the end, we discuss how to reduce the tuning bias, guided by the theories we developed.
Many conformal prediction methods utilize a hold-out set for parameter tuning. in addition to the calibration set. For example, (1) RAPS (Angelopoulos al., 2021) and SAPS (Huang al., 2024) search their parameters on the hold-out set; (2) score aggregation methods (Fan et al., 2024; Luo & Zhou, 2024; Yang & Kuchibhotla, 2024) optimize the selection or weights for candidate scores; (3) confidence calibration methods (Dabah & Tirer, 2024; Guo et al., 2017;
Xi al., 2024) tune the scale parameters for better cali- bration; (4) training methods (Liu et al., 2025; Stutz et al.. 2022) fine-tune models on the hold-out set. Previous works claim that leveraging the same hold-out set for tuning and calibration will destroy the exchangeability (Angelopoulos et al., 2021; Dabah & Tirer, 2024; Xi et al., 2024; Yang & Kuchibhotla, 2024), but they did not provide a formal quan- tification on the coverage gap introduced by the violation of exchangeability systematically. This prompts us investi- gate the influence of parameter tuning the coverage gap in the absence of a hold-out set.
1. Introduction
In this work, we reveal a previously unrecognized phe- nomenon: the tuning bias - the coverage gap introduced by using the same dataset for tuning and calibration, is neg- ligible for simple parameter tuning conformal prediction methods. Empirically, we find that most methods maintain their coverage rates, except for vector scaling (Guo et al., 2017) and the fine-tuning version of ConfTr (Stutz et al., 2022). Furthermore, we observe the parametric scaling law of the tuning bias: this bias increases with parameter space complexity and decreases with calibration set size. An intuitive explanation for this phenomenon is that models with more complex parameter space require more data to tune for the optimal parameters.
Quantifying uncertainty in predictions is crucial for the safe deployment of machine learning, particularly in high-risk domains such as financial decision-making and medical di- agnostics. Conformal prediction stands out promising statistical framework for quantifying uncertainty in the pre- dictions of any predictive algorithm (Papadopoulos, 2008; Vovk, 2012; Vovk et al., 2005). It transforms point pre- dictions into prediction sets guaranteed to contain ground truths with user-specified coverage rate. Under the as- sumption of data exchangeability, these prediction sets offer non-asympiotic coverage guarantees without distributional assumptions. However, the assumption may not always hold
'qqual contribution 'Department of Statistics and Data Science, Southern University of Science and Technology 'Department of Computer and Information Science, University of Macau.. Corre- spondence to: Hongxin Wei <weihx @ sus.ech.edu.cn>>
Formally, we propose a theoretical framework to quantify the tuning bias, which is formulated as a specifically de- signed constrained ERM problem (Bai et al., 2022). In particular, we measure the tuning bias using the classical
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'Code: https:/ http::::/ggttbbb..mmmmm-sssststt wtw.s//w....ommmmmtttttttttt-- Sustech/ Parametric- Scal Eng-Law- CP- Tuning.

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
empirical process within the extended parameter space (van der Vaart & Wellner, 1996). Furthermore, we derive the upper bounds of tuning bias in the cases of finite and infinite parameter spaces, respectively. We then provide rigorous proof for the parametric scaling law of tuning bias through the upper bounds, which aligns with empirical observations. Finally, we present the tuning biases of parameter tuning in several conformal prediction methods, such as RAPS, score aggregation, and confidence calibration methods.
i such that the probability of observing scores on test sam- ples below the threshold satisfies pre-specified error rate a. Specifically, we determine the threshold by finding the
(1 a)-th empirical quantile of the calibration scores:
i = inf {s li S(z,, y:) S s 2 [(n + +) - a)
(2)
For the test step with a given feature of test sample æ. the non-conformity score is computed for each label y E V. The prediction set C(x) is constructed by including all labels whose non-conformity scores are below the threshold i:
We further discuss the potential solutions to mitigate tuning bias. With the parametric scaling law, we could increase the size of the calibration set or reduce the complexity of the parameter space to reduce the tuning bias. The former may not be practical due to data scarcity. On the latter, we discuss two cases: one is to reduce the number of parameters to tune; the other is to apply regularization the parameter space. Our main contributions are summarized as follows:
C(2) := Cxxx) = {v e y: S( v) S f}
(3)
where the notation 7 used to emphasize its dependence on the calibration set Deat. Here we consider a little weaker version of independence:
Definition 2.1 (Exchangeability). The samples from D are exchangeabee if and only if the joint distribution of these samples is invariant under any permutation of the indices of the samples in D.
We identify a new phenomenon: simple parameter tuning in many conformal prediction methods leads to negligible tuning bias, where we leverage the same dataset for tuning and calibration.
With the assumption of exchangeability. the conformal pre- diction set C(ar) in Eq. (3) has finite-sample coverage guarantee:
We present the parametric scaling law of tuning bias: this bias increases with parameter space complexity and decreases with calibration set size.
Theorem 2.2. (Barber et al., 2023; Lei et al., 2018) If the samples from Deot and the test sample (x, y) are exchange- able, the conformal prediction set defined in Eq. (3) satisfies
We establish a theoretical framework to quantify tuning bias and rigorously prove the parametric scaling law of tuning bias via its upper bounds.
1 - S e 1 aa-
n+1
If the assumption of exchangeability does not hold, there could be a large deviation in the coverage rate. We could use the coverage gap to measure the conformal predictor C for a given error rate a and test sample (xc ())
We discuss the potential application of our theoretical results and explain order-preserving regularization as possible solution to reduce tuning bias.
2. Background
CovGap(C) := [(1 ( a) Ply E C(x))).
Conformal prediction Conformal prediction (Vovk et al., 2005) aims to produce prediction sets that contain ground- truth labels with a desired coverage rate. Let X' C I denote the input space and y' denote the label space. Formally, the goal of conformal prediction is to construct a set-valued mapping C: X + 2 that satisfies the marginal coverage:
Parameter tuning Parameter tuning is a common practice in conformal prediction. We characterize the parameter tun- ing as follows. Given a score function S, we can transform it using function a to obtain S = S E ( : X'x + RJ. When this transformation is parameterized by À E A. where A is the parameter space, we denote the transformed score as S for simplicity. There are some examples:
PP E C(x)) 2 a- a,
RAPS (Angelopoulos et al., 2021) uses scalar À and an integral tune the best score function on hold-out set, and so does SAPS (Huang al., 2024).
for a user-specified error rate a E (0, where input X. and output y E y. As widely used proce- dure, split conformal prediction (Papadopoulos, 2008) initi- ates with calibration step. For each sample (x;, yı) from the calibration set De. == ((v,, y:) H we compute the non-conformity score s; := S(z,, y/.) for a score function S X x' + R. The non-conformity score function S mea- sures the strangeness of given sample. Based on the scores computed on the calibration set, we search for threshold
For selection and aggregation of scores problems (Fan et al., 2024; Ge et al., 2024; Luo & Zhou, 2024; Yang & Kuchibhotla, 2024), the optimal score function or weight vector is obtained from a finite number of can- didates. The selection or weights could be viewed as the transformation parameter to tune.
2

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Conformal prediction with confidence calibration (Dabah & Tirer, 2024; Guo et al., 2017; Xi al., 2024) uses single positive scalar À > 0 or vector À E IRK to calibrate deep learning classifiers.
10
hold-out
same
CovGap (%)
(%)
For training models from scratch in conformal predic- tion, they could be modified as post-training method. Researchers fine-tune the fully connected layer or an appended layer, and the efficiency of conformal predic- tors could be enhanced (Huang et al., 2023; Liu et al., 2025; Stutz et al., 2022). The parameters in the layer could be viewed as the transformation parameter.
RAPS
SAPS
SA
C-Adaprer
ConfTrift.)
These practices tune their parameters using a hold-out set that is separate from the one used for conformal prediction calibration. Given the transformation parameter A, we can calculate the threshold f in Eq. (2) with parameter X. If we use the same set for both parameter tuning and conformal prediction calibration, it will destroy the data exchange- ability assumption and probably introduce an additional coverage gap. We defined the additional coverage gap as:
Figure 1. Tuning biases of various methods in conformal pre- diction, using ResNet- 18 on CIFAR-I00 at a 0.1. The APS used except for RAPS, SAPS and SA, with a calibration set size of 1000. The "hold-out" and "same" denote that we use separate/same datasets for parameter tuning and calibration, respectively. Tuning bias the difference between the coverage gaps of models tuned in the setting of hold-out and same.
Definition 2.3 (Tuning Bias). For the conformal prediction with parameter tuning, C, the tuning bias for parameter tuning on the same set as the calibration set is defined as the additional coverage gap caused by the practice, i.e.,
In particular, the insight in this work may inspire future works in non-exchangeable conformal prediction.
TuningBias(C) CovGap(C) CovGap(Cnulld-oll
It could also answer the concern, "why not split the dataser", for the same reasons. Indeed, it is easy to split the validation set when the provided data is sufficient. However, it can be particularly important to consider data reusing in data-scarce scenarios, like rare diseases, natural disaster prediction, and privacy-constrained constraiied personal data. With limited data, sep- arating the dataset will further exacerbate the data scarcity problem, compromising the effectiveness of both conformal calibration and parameter tuning. In addition, exploring the tuning bias could provide an in-depth understanding of the exchangeability assumption, which may inspire future works non-exchangeable CP.
where C is the conformal predictor with parameter tuned on the same set as the calibration set, and Chold is the conformal predictor with parameter tuning using a hold-out set separated from the set used for conformal prediction.
Remark 2.4. Here, we clarify that understanding the tuning bias is crucial in conformal prediction practice:
For data-scarce scenarios, splitting the calibration dataset is impractical in data-scarce scenarios like rare diseases, natural disaster prediction, and privacy- constrained personal data. With limited data, using separated datasets will reduce points for parameter tuning and conformal calibration, compromising the approach's 's effectiveness and stability. Thus, it's valu- able to assess when splitting is needed, or data reuse is permissible rather than sticking to traditional practices.
In the next section, we first conduct extensive empir- ical study of various conformal prediction methods with parameter tuning. Then, we explore how the complexity of parameter space and the size of the calibration set influence tuning bias, respectively. We empirically demonstrate the scaling laws of tuning bias on the complexity of parameter space and the size of the calibration set.
For simple implementation, even with sufficient data, maintaining separate sets can increase the pipeline com- plexity. Understanding when this separation is unneces- sary-such as when tuning bias is cectiiibl-ennalle simpler, more streamlined workflows while preserving coverage guarantees, offering practical relevance.
3. Empirical Study
3.1. Tuning Bias of Current Methods
We empirically investigate the potential influences of the tun- ing bias. The methods considered here include RAPS (An- gelopoulos et al., 2021), SAPS (Huang et al., 2024), score aggregation (Luo & Zhou, 2024, SA), temperature scaling
For foundational understanding, exploring the tun- ing bias can provide an in-depth understanding of the exchangeability assumption in conformal prediction.
3

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
(TS), vector scaling (VS) (Dabah & Tirer, 2024; Guo et al., 2017; Xi et al., 2024), C-Adapter (Liu et al., 2025), and the fine-tuning version of ConfTr (Stutz et al., 2022). We con- duct experiments on the CIFAR- 100 dataset (Krizhevsky, 2009) and use pre-trained model ResNet-18 18 (He et al., 2016). The introduction of methods and detailed experimental setup are provided in Appendix A. The size of the calibration set considered here is 1000. We use separate or the same datasets for parameter tuning and calibration, respectively. For each experiment, the test set comprises the remaining data. By default, we use the APS score for experiments involving confidence calibration and conformal training.
As shown in Figure (a), the tuning bias increases with the number of unfrozen parameters in vector scaling. With larger number of parameters, the tuning bias increases by more than 50% compared to the lower number of param- eter spaces. In general conclusions in learning theory, the higher number of parameters to tune means more complex parameter space without additional constraints. The more complex parameter space leads to more generalization bias. Here, our empirical results also support this conclusion: the tuning bias scales with the complexity of parameter space.
The effect of calibration set size Then, we consider the tuning bias under different sizes of the calibration set on Figure 2 (b). The calibration set size varies from 6000 to 10000 with an increment of 1000. The parameter tuning method used here is vector scaling with full parameter space. For the size of the calibration set, the tuning bias decreases with the size of the calibration set increasing, in Figure 2 (b). The tuning bias decreases about 50% from the size of 6000 to 10000. As the size of the calibration set increases, the tuning bias approaches zero. The empirical results support the conclusion that the tuning bias scales down with the size of the calibration set.
Tuning bias is not always negligible for the parameter tuning in conformal prediction. In Figure 1, we present the tuning biases caused by various tuning methods using ResNet-18 18 on CIFAR-100. The results indicate that most methods do not introduce significant tuning biases, achiev- ing similar coverage gaps regardless of whether the same dataset separate datasets are used for calibration and tun- ing. For example, the coverage gaps of RAPS using the same and separate datasets are almost identical, as shown in Figure 1. However, in vector scaling and ConfTr (ft.), using the same datasets could result in much larger coverage gaps than using hold-out dataset for tuning. We conjecture that these differences may be due the large number of parameters tuned in these methods. In what follows, we provide in dn-hepth analyses to explore the factors influencing tuning biases in these methods.
shown
3.3. Intuitive Explanation
Combining the above two empirical results, we could see the tuning bias scales up with the complexity of parameter space and down with the size of the calibration set empiri- cally. Based on the framework of learnability of conformal prediction (Bai et al., 2022; Gupta et al., 2022), we could reinterpret the threshold calculation step Eq. (2) as solving a constrained empirical risk minimization (ERM) problem with a single learnable parameter:
3.2. Parametric Scaling Laws of Tuning Bias
We conduct an additional analysis from two key perspec- tives: (1) the number of parameters and (2) the size of the calibration set. The experiments provide deeper insights into how tuning methods influence bias formation. By the convention to control the number of unfrozen parameters, we focus on confidence calibration using vector scaling. We could control the number of unfrozen parameters by freez- ing a portion of the parameters in vector scaling. freeze a portion of the parameters in vector scaling. In detail, we do not let the proportion of the parameters be optimized randomly. The ratio of frozen parameters ranges from 0% to 40% by 10% increments. The detail of vector scaling is provided in Appendix A.2. We use separate or the same datasets for parameter tuning and calibration, respectively, with APS. All methods of conformal prediction are under the same error rate a 0. To ensure the reliability of our results, we repeat each experiment 30 times and report both the average result and its corresponding standard deviation.
Σ (((aa))//n
= arg min
VEI
such that
Mu & ((o))//n Σ
IE
where Teai is the index set of the hold-out set Deal. Then, the tuning parameter in the conformal prediction could be placed into the optimization problem with the learnable pa- rameter (X, According to the general results in ERM theory, a more complex parameter space requires more data to learn the optimal tuning parameters. These results intu- itively explain the phenomenon that appears above. Further, we will quantify the parametric scaling law of the tuning bias on the complexity of parameter space and the size of the calibration set, respectively, under the constrained ERM framework. To our knowledge, we are the first to explore this framework for the Icarnability of tuning parameters in the context of conformal prediction. Based on the learn- ability of tuning parameters in the context of conformal prediction, we further establish the theoretical results of the
The tuning bias scales up with the complexity of pa- rameter space. We first consider the tuning bias under a different number of unfrozen parameters in Figure (a).
4

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
12
Reuse Standard
Coverage Gap (%)
hold-out
CovGap (%)
4-
1200
1400
1600
1800
2000
6000
7000
8000
9000
10000
Amounts of Parameters
Size of Calibration Set
(a) The complexity of parameter space.
(b) The size of the calibration set.
Figure Parametric scaling law, on (a) the complexity of parameter space (b) the size of the calibration set, using ResNet- on ImageNet using APS. The calibration set size for Figure (a) is 6000. The 'hold-out' and 'same' denote that we use separate/same datasets for parameter tuning and calibration, respectively. Tuning bias the difference between the coverage gaps models tuned in setting of hold-out and same. The tuning bias scales up with the number of parameters and scales down with the size of the calibration set.
tuning bias in the following section.
We formulate the parameter tuning using the same set as the calibration set for conformal prediction as follows: the tuning parameter À is selected by minimizing pre-specified loss function & on the calibration set Deal
In summary, the empirical results reveal that the tuning bias is negligible for simple parameter tuning and scales up with the complexity of parameter space and down with the size of the calibration set. We intuitively explain the empirical results using the learnability of tuning parameters in the context of conformal prediction. Next, we will provide the theoretical results of the tuning bias in the following section.
A Ap arg min EA, ST.)) XEA
The conformal prediction set with parameter tuning is refor- mulated as:
C(x) = (x).
(5)
4. Theoretical Results
Tuning bias While this procedure appears straightforward, using the same set for both parameter tuning and confor- mal prediction introduces a tuning bias. To understand this phenomenon, 1et us examine why the standard split con- formal prediction works. The validity guarantee Eq. (1) relies the exchangeability assumption specifically, the score function S is independent of the calibration set D This independence ensures that the score of a test sample S(Twa Mest) is exchangeable with the scores of calibration samples (S(x, ys) (æ:; y:) E Deat)- However, we reuse the same set for both parameter tuning and calibra- tion for conformal prediction, this crucial exchangeability property is violated. The transformed score Sd depends on the calibration set Deal through the parameter selection process. Consequently, the scores of test samples lose their exchangeability with the scores of calibration samples, in- validating the coverage guarantee in Eq. (1). To understand this phenomenon mathematically we demonstrate the cover- age gap for the conformal prediction with parameter tuning by decomposing the coverage gap into two components:
In this section, we provide the theoretical results for the tuning bias. We first introduce the problem formulation in Section 4.1. We introduce the tuning bias in general cases. Then, we consider the theoretical results of the tuning bias in finite and infinite parameter cases in Section 4.2 and Section 4.3, respectively. The application of these results to some specific cases is also considered.
4.1. Problem Formulation
For score function S* with X E A, the prediction set is defined as:
< st},
where t is threshold. Given dataset D. we denote the set of scores under parameter À as S = { (ax, y1) (x,, y:) E D} and Sp : [S(x, y:) (x, y:) E D}. The associated threshold for S is defined as:
i/ = Q( (((-a)((+)))(SS))
(4)
Theorem 4.1 (Coverage gap for conformal prediction with parameter tuning). If the samples in Deat Due are inde- pendent and identically distributed, then the coverage gap
where (p(S) denotes the p-th empirical quantile of non- empty set (p(S) = inf(g: [[s S q)l 2 p|S]).
5

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
of the conformal prediction set with parameter tuning C defined in Eq. (5) are bounded as follows:
any finite parameter space A. The examples include param- eter tuning in some specific score functions (Angelopoulos et al., 2021; Huang et al., 2024), score selection (Yang & Kuchibhotla, 2024) and aggregation (Luo & Zhou, 2024) with finite candidates, and early stopping in conformal pre- diction (Liang et al., 2023) and so on.
CovGap(C) S T + Ea,n:
(1 is the coverage gap of the slandard split conformal prediction set with the size of the calibration set and error rate a, and the term RA with T C IR,
where Ea." :=
-
Application to parameter tuning in RAPS score The Regularized Adaptive Prediction Sets (RAPS) method (An- gelopoulos et al., 2021) introduces score function that requires tuning two hyperparameters:
RA == sup 1 Σ ((5A st)
AEA,ET
vE(m]
SRAPS (2., y. p) Savs( y.P) + (o(y, Kreg) )
P (SS Frest) S tt (eea))
where SAPS is defined in Eq. (9), oly, p) represents the rank of probability p(y]z) among all possible classes, p(y' (e' E [K]), and y and kreg are hyperparameters. The notation (z)* signifies the positive part of 2. The RAPS method optimize the set size or adaptiveness with hyperpa- rameters À = (7, kigg) from a predetermined finite param- eter space ARAPS| = M - K where M is the number of grid points for 7, and K is the pre-specified max number of classes (Angelopoulos et al., 2021). The tuning bias is bounded by Proposition 4.2 follows:
The proof of Theorem 4.1 is provided in Appendix E. The upper bound of the coverage gap could be decomposed into two components: AERA and En.n. The first term, ERRA, in- troduces additional bound for the coverage gap, which is not present in the standard conformal prediction framework, containing only the second term, Ea,n. As the definition of tuning bias in Definition 2.3, we could conclude that
(C)) - ERA-
In fact ERA is closely related to the classical empirical process theory (van der Vaart & Wellner, 1996; Vershynin, 2018). We could define the class associated with N, as:
Corollary 4.3. For a classification problem and the hold- out set size n, the tuning bias of RAPS is bounded by:
log(2MK)
1
TumingBias(CRaps)
HA = (1( s A, A,
2n
2nl log((Mg]
The bound A the empirical process on the class HA:
The proof of Corollary 4.3 is provided in Appendix G. AI- though the RAPS method (A (Angelopoulos et al., 2021) recom- mends using an additional hold-out set for hyperparameter selection, our findings allow for direct hyperparameter se- lection without the need for an extra hold-out set. As for SAPS (Huang et al., 2024), the parameter space is also finite, and we could also apply the same analysis to SAPS.
1 Σ n
ERAA = E sup GEMH
g(a, V:) EE(ggE(geee Ihea)) Deal vE[m)
depends on the complexity of parameter space A. The- orem 4.1 is a general result that applies to any parameter space A without any constraint. Next, we provide the bound analysis of the tuning bias in finite and infinite parameter space and consider several applications using these results.
Application to score selection with finite candidate Con- sidering there are M candidate score functions {Smm m E [M] for constructing conformal prediction sets, let Cyn (az) be the prediction set obtained using score function S.,, at a given error rate a. The optimal score function is selected by minimizing the empirical size of the prediction set:
4.2. Tuning Bias in Finite Parameter Space
When the parameter space A is finite, we bound the tun- ing bias using classical concentration inequality, Dvoret- -oy-Kiefer-Wolfowiizz inequality (Dvoretzky et al., 1956), on the empirical process with the finite union of probability: Proposition 4.2. For a fiitt parameter space A, we have
r = arg min mE (E M)
Σ 1E
ICm (2::1///ZlZll
This selection process introduces tuning bias that can be bounded using Proposition 4.2 with |A| M. This case is also considered by the score selection issues (Yang & Kuchibhotla, 2024). They propose a score selection frame- work for constructing minimal conformal prediction regions by selecting optimal score functions from finite candidates.
log(2)Al)
TuningBias <
2n
22 (Tg((2A)))
The proof of Proposition 4.2 is provided in Appendix F. The result in Proposition& 4.2 is a general result that applies to
6

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Their work introduces two methods. The first optimizes prediction width using the same hold-out set as the calibra- tion set of conformal prediction, and the second maintains coverage guarantees using separate hold-out set. The first achieves minimal prediction interval width with approxi- mate coverage guarantees. It provides a bound of coverage gap for the first method, as special case of our result:
to any infinite parameter space A C R4. It shows that the tuning bias increases with the dimension of parameter space d and decreases with the size of the hold-out set n. Next, we will present an application for confidence calibration.
Application to confidence calibration Consider classi- fication problem with K classes, where we have two confi- dence calibration methods: Temperature scaling (TS) and vector sealing (VS) (Dabah & Tirer, 2024; Guo et al., 2017; 7; Xi et al., 2024). The details of temperature scaling and vector scaling with tuning parameter À are given in Ap- pendix A.2. For the two methods, there is a significant difference in the dimension of parameter space A: For tem- perature scaling, the parameter space is Ars Rt, contain- ing only one positive real number X. For vector scaling, the parameter space is Avs = R x RK containing 2K param- eters. Since vector scaling has a more complex parameter space compared to temperature scaling, the tuning bias of vector scaling larger than that of temperature scaling:
Corollary 4.4. For a classification problem, and the hold- out set size n, the tuning bias of selection of score func- tions (Yang& & Kuchibhotla, 2024) with the number of candi- dates M is bounded by:
log((M) (2M)
TiningBias(C) S
2n
V 2n 2 (2g(
The proof of Corollary 4.4 is provided in Appendix G. For the score aggregation (Luo & Zhou, 2024), we analyze it in Appendix L. Next, we extend our analysis to an infinite parameter space and apply it to conformal prediction with confidence calibration, where the parameter space is infinite.
Corollary 4.7. For a classification problem with K classes, the calibration set size n and the same pre-trained model, the tuning bias of temperature scaling is smaller than that of vector scaling: TuningBias(rrs) S TaningBias where Crs and Cus are the prediction sets of temperature scaling and vector scaling, respectively.
4.3. Tuning Bias in Infinite Parameter Space
Before introducing the infinite parameter case, we first in- troduce the concept of Vapnik-Chervone Chenii-Chervonenkis (VC) dimen- sion (Vapnik& & Chervonenkis, 1971). VC-dimension is measure of the complexity of classes of Boolean functions.
The proof of Corollary 4.7 is provided in Appendix I. The result shows that the tuning bias of temperature scaling is smaller than that of vector scaling. We provide a result for the binary classification case in Section 5, where the tuning bias of temperature scaling is zero.
Definition 4.5 (VC Dimension). Let F be a class of Boolean functions defined on a domain Ω, f: - {0, 1} for all f E F.A. A subset S2' C Ω is said to be shattered by F any functiin g: : 52' - {0, 1} can be obtained by restrict- ing some function f E F onto S The VC dimension of F, denoted by VC(F), is the size of the largest subset S' C Ω that can be shattered by F. If the size of the largest shattered subset is infinite, we say the VC dimension is infinite.
In this section, we derive the upper bounds of tuning bias in finite and infinite spaces, proving the parametric scaling law of tuning bias, and provide examples including RAPS, score selection and confidence calibration. Next, we discuss how to reduce the tuning bias with two specific cases.
Although the concept may seem hard to understand, it can be viewed as the maximum number of points that the class of functions can shatter intuitively. With more complex class of functions, it is more likely shatter a larger number of points. It is measure of the complexity of the class of functions, F. The intuition is that the larger the complexity of the class of functions, the larger the bound of the empir- ical process is. By the definition of H. and Lemma D.6 in Appendix D, we develop a general bound of the tuning bias: Proposition 4.6. For an infinite parameter space A C Rdd we have the tuning bias is bounded by:
5. Discussion of Potential Solutions
In the previous analysis, we demonstrate the parametric scaling law of tuning bias in relation parameter space complexity and calibration set size. Here, we provide an initial discussion of potential solutions to mitigate the tuning bias that arises from using the same data for both calibra- tion and parameter tuning. It is important to note that the common practice is to use separate hold-out datasets for calibration and parameter tuning. Mitigating tuning bias can be particularly beneficial in real-world applications when splitting the dataset is impractical due to data scarcity.
TumingBias (C) S SCV n
for some universal constant C > 0.
Following the scaling law, we can implement two principles to reduce the tuning bias: increasing the size of calibra- tion sets or reducing the complexity of tuning parameters. The former indicates that we can decrease the bias by col-
The proof of Proposition 4.6 is provided in Appendix H. The bound in Proposition 4.6 is a general result that applies
7

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
lecting more data points for the calibration set, but it is challenging in data-scarce scenarios. We then focus the latter- - reducing the complexity of tuning parameters, which is commonly implemented to address overfitting issues. In the following, we discuss this principle with two special cases of parameter tuning in split conformal prediction.
tions: (aa,, y), o(y, x.,p) p) = oly, at Px) where o(y, x) is the order of the true label y in the sorted predicted probabil- ities p(-lær), and Pa is the probability after transformation A. Taking ConfTr (Stutz et al., 2022) as the tuning algorithm on the final linear layer, we present the following proposition to show the benefit of the order-preserving constraint.
Table 1. Tuning bias comparison various methods. The cal-
Proposition 5.2. For classification problem with K classes, and the calibration set size n, we have the tun- ing bias of Cop is less than the one C: TuningBias(Cop) S TuningBias(C), where C and Cop represent the prediction sets of models tuned by Confir; with Cop under the order- preserving constraint and C without it.
ibration set size is 2500 for CIFAR- 100 and 5000 for ImageNet using APS, Results in bold indicate superior performance.
Methods
CIFAR-100 (%)
ImageNet (%)
Temperature scaling
0.14 + 0.01
0.04 0.01
Vector scaling
1.13 1 0.02
6.63 0.03
ConfTr (ft.) w/ OP
0.52 + 0.37
0.40 0.31
ConfTr (fi.) w/o OP
6.15 + 0.86
21.68 + 0.58
The proof of Proposition 5.2 provided in Appendix K. And by Lemma K.I, the dimension of parameter space of order- preserving vector scaling 2. which much smaller than that without constraint, 2K. By Lemma K.3, the dimension of parameter space of ConfTr with order-preserving con- straint is K + 2, which is much smaller than that of matrix scaling with its dimension being K2+ We also verify the argument by the empirical results shown in Table 1. The tun- ing bias of ConfTr with prder-preserving constraint is much smaller than that without it. This approach is advantageous as it can generalize complex paradigms of parameter tuning (e.g., fine-tuning the final layer). It is worth noting that designing tailored regularization techniques for specific tuning methods in conformal prediction may be a promising direction for future research.
Reducing the parameter number A straightforward way to constrain parameter complexity is to reduce the number of parameters in model tuning. Here, we provide an example of parameter reduction through weight sharing. In particular, we show the benefits of weight sharing by comparing the tuning biases of temperature scaling (TS) and vector scaling special case of
(VS), where the former can be viewed vector scaling with a shared parameter |Ars| < |Avs]- The empirical results in Table I show that TS with fewer param- eters achieves much smaller tuning biases than VS, which is also supported by Figure I and Figure 3. Theoretically, we provide a theoretical result for the comparison in the case of binary classification:
Proposition 5.1. For a binary classification problem, we have TuningBias(Crs) = < TuningBius(Crs) where Cis and Cyy are the prediction sets of models tuned by tempera- ture scaling and vector scaling, respectively.
6. Related Works
Conformal prediction Conformal prediction is method for uncertainty quantification that ensures that the predic- tion intervals or sets cover the true label with a user-defined error rate (Papadopoulos, 2008; Vovk, 2012; Vovk et al., 2005). On the one hand, conditional coverage validity is a key property of conformal prediction, ensuring the algo- rithm fairness (Angelopoulos al., 2021; Gibbs et al., 2024; Huang et al., 2024; Romano et al., 2020). On the other hand, to enhance the efficiency of conformal prediction, recent studies (Kiyani et al., 2024a;b; Liu et al., 2025; Stutz et al., 2022) have proposed training-based methods, which could be regarded as adapters, performing tuning prior to confor- mal prediction. Beyond these, with many non-conformity scores proposed, the score selection or aggregation is an- other challenge in conformal prediction (Fan et al., 2024; Gasparin & Ramdas, 2024; Ge et al., 2024; Luo & Zhou, 2024; Qin et al., 2024; Yang & Kuchibhotla, 2024). These recent paradigms of conformal prediction typically require tuning parameters on a hold-out dataset, and our work pro- vides the first study to quantify the negative effect induced by using the same dataset for tuning and calibration.
We provide the proof of the above proposition in Appendix From the example, we demonstrate that designing tuning algorithms with few parameters will be beneficial in prevent- ing the tuning bias. Also, we analyze the relationship be- tween the number of parameters and tuning bias by freezing different numbers of parameters within VS. The results in Figure 2 (a) show that increasing the number of parameters leads to higher tuning bias, supporting the claim. However, reducing the parameter number may severely degrade the performance of parameter tuning, making inapplicable in some scenarios, which motivates us to apply regularization to the tuning algorithm.
Regularization in the tuning Another effective approach is the use of regularization methods, which introduce ad- ditional constraints or penalties to model parameters, pre- dictions, or loss functions. Here, we present an example of applying an pndee-ires constraint to model predic-
8

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Learnability As classical learnability theory, learnable model could be regarded as risk minimization model with specific hypothesis class (van der Vaart & Wellner, 1996; Vapnik, 1991; 1999; Vapnik & Chervonenkis, 1971; Ver- shynin, 2018). And further, the constrained ERM is de- veloped as a special case of Icarnability theory, where the hypothesis class is the set with a specific constraint or struc- ture, such as structural risk minimization of character recog- nition (Guyon et al., 1991), of data-dependent hypothesis class "Shawe-Taylon et al., 1998), of Rademacher penalty method (Koltchinskii, 2001) and rough set-based classi- fier (Liu et al., 2020). As for conformal prediction, several works study learn the conformal prediction directly by de- signing a specific objective function (Noorani et al., 2024; Stutz et al., 2022). Further, the conformal prediction a spe- cial case of risk minimization problem with the constraint of coverage guarantee, and the generalization loss for the size of prediction set could be quantified (Gupta et al., 2022; Yang & Kuchibhotla, 2024), including classification (Bai et al., 2022) and regression (Fan et al., 2024; Gupta et al., 2022). As we proposed in Section 4, we interpret the tuning bias as a further constrained risk minimization problem of conformal prediction and provide the first systematic theo- retical analysis of the tuning bias, offering a novel tool for analyzing the learnability of general conformal prediction problems.
Acknowledgement
We thank the anonymous reviewers for their valuable comments and suggestions. This research is supported by the Shenzhen Fundamental Research Program (Grant No.JCCY20220880709110 1090020), the SUSTech-NUS Joint Research Program and in part by the National Natural Sci- ence Foundation of China (NSFC) under grant 1237 1290. We gratefully acknowledge the support of the Center for Computational Science and Engineering at the Southern University of Science and Technology.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Angelopoulos, A. N., Bates, S., Jordan, M., and Malik, J. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021.
Bai, Y., Mei, S., Wang, H., Zhou, Y., and Xiong, C. Efficient and differentiable conformal prediction with general func- tion classes, In International Conference on Learning Representations, 2022.
7. Conclusion
In this paper, we first uncover an unobservable phenomenon related the tuning bias in conformal prediction with pa- rameter tuning. Empirically, we observe that the tuning bias is negligible when the parameter space's complexity is low, and the hold-out set is sufficiently large. Our theoretical find- ings establish a parametric scaling law for the tuning bias. Additionally, we explore potential solutions to address the implications of our theoretical results, emphasizing strate- gies to mitigate tuning bias by reducing the complexity of the parameter space. For future research, incorporating the structure of the parameter space could improve the precision of our theoretical results.
Barber, R. F., Candès, E. J., Ramdas, A., and Tibshirani, R. J. Conformal prediction beyond exchangeability. The Annals of Statistics, 51:816-845, 2023.
Dabah, L. and Tirer, T. On temperature scaling and confor- mal prediction of deep classifiers. arXiv preprint arXiv: 2402.05806, 2024.
Dvoretzky, A., Kiefer, J., and Wolfowitz, J. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27:642-669, 1956.
Fan, J., Ge, J., and Mukherjee, D. UTOPIA: Universally trainable optimal prediction intervals aggregation. arXiv preprint arXiv: 2306. 16549, 2024.
Limitation Our theoretical results provide unified frame- work for understanding uning bias a general phenomenon in conformal prediction. However, the bound of tuning bias not tight without more assumptions on the modelling. The bound could be more precise with more assumptions the modelling. Here, we provide an example of regularization on the lcarnability for conformal prediction, which roughly tightens tuning bias. The tuning bias could be more pre- cise under more assumptions on the modelling, such as the structure of the score and transformation.
Gasparin, M. and Ramdas, A. Conformal online model aggregation. arXiv preprint arXiv: 2403. 2024.
Ge, J., Mukherjee, D.,, and Fan, J. Optimal aggregation of prediction intervals under unsupervised domain shift. Neural Information Processing Systems, volume 37. Curran Associates, Inc., 2024.

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Gibbs, I., Cherian, J. J., and Candès, E. J. Conformal prediction with conditional guarantees. arXiv preprint arXiv; 12616, 2024.
Liang, R., Zhu, W., and Barber, R. Conformal prediction after efficiency-orientedd model selection. arXiv preprint arXiv: 2408.07066, 2024.
Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning, pp. 1321-1330 PMLR, 2017.
Liang, Z., Zhou, Y., and Sesia, M. Conformal inference is (almost) free for neural networks trained with early stopping. In Proceedings of the 40th International Con- ference on Machine Learning, pp. 20810-20857 PMLR, 2023.
Gupta, C., Kuchibhotla, A. K., and Ramdas, A. Nested conformal prediction and quantile out-of-bag ensemble methods. Puttern Recognition, 127:108496, 2022.
Liu, J., Bai, M., Jiang, N., and Yu, D. Structural risk mini- mization of rough set-based classifier. Soft Computing, 24:2049-2066, 2020.
Guyon, I., Vapnik, V., Boser, B., Bottou, L.,, and Solla, S. A. Structural risk minimization for character recognition. In Neural Information Processing Systems, volume 4. Curran Associates, Inc., 1991.
Liu, K., Zeng, H., Huang, J., Zhuang, H., Vong, C. M., and Wei, H. C-adapter: Adapting deep classifiers for efficient conformal prediction sets. In The Thirteenth International Conference on Learning Representations, 2025.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEF Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Luo, R. and Zhou, Z. Weighted aggregation of confor- mity scores for classification. arXiv preprint arXiv: 2407.102300 2024.
Huang, J., Xi, H., Zhang, L., Yao, H., Qiu, Y., and Wei, H. Conformal prediction for deep classifier via label ranking. In Proceedings of the 4 slst International Conference Machine Learning, Proceedings of Machine Learning Research, pp. 20331-20347. PMLR, 2024.
Massart, P. The tight constant in the Dvoretzky-Kiefe Kiefer- Wolfowitz inequality. The Annals of Probability, 18: 1269-1283, 1990.
Huang, K., Jin, Y., Candes, E., and Leskovec, J. Uncertainty quantification over graph with conformalized graph neu- ral networks. In Neural Information Processing Systems, volume 36, pp. 26699-26721. Curran Associates, Inc., 2023.
Noorani, S., Romero, O., Fabbro, N. D., Hassani, H., and Pappas, G. J. Conformal risk minimization with variance reduction. arXiv preprint arXiv: 24/ 1.01696, 2024.
Oliveira, R. I., Orenstein, P., Ramos, T., and Romano, J. V. Split conformal prediction and non-exchangeable data. Journal of Machine Learning Research, 25:1-38, 2024.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv: 14/2.6980, 2017.
Papadopoulos, H. Inductive conformal prediction: Theory and application to neural networks. In Tools in Artificial Intelligence. IntechOpen, 2008
Kiyani, S., Pappas, G. J., and Hassani, H. Conformal pre-
diction with learned features. In Proceedings of the 41st International Conference on Machine Learning, 2024a.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L.. Desmaison, A.. Köpf, A., Yang, E., De Vito. Z.. Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. PyTorch: An imperative style, nigh-performance deep learning library. In Neural Infor- mation Processing Systems, volume 32, pp. Curran Associates Inc., 2019.
Kiyani, S., Pappas, G. J., and Hassani, H. Length opti- mization in conformal prediction. In Neural Information Processing Systems, volume 37. Curran Associates, Inc., 2024b.
Koltchinskii, V. Rademacher penalties and structural risk minimization. IEEE Transactions Information Theory, 47:1902-1914, 2001.
Krizhevsky, Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009.
Platt, J. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Ad- vances in Large Margin Classifiers, 10:61-74, 1999.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. Distribution-free predictive inference for regression. Journal of the American Statistical Associa- tion, 11:1004411111 2018.
Qin, S., He, J., Gang, B., and Xia, Y. SAT: Data-light uncertainty set merging via synthetics, aggregation, and test inversion. arXiv preprint arXiv: 2410.12201 2024.
10

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Romano, Y., Sesia, M., and Candès, E. J. Classification with valid and adaptive coverage. arXiv preprint arXiv: 2006.02544, 33:3581-3591, 2020.
Sadinle, M., Lei, J., and Wasserman, L. Least ambiguous set-valued classifiers with bounded error levels. arXiv preprint arXiv: 1609.00451, 114:223-234, 2019.
Shawe- Taalee J., Bartlett, P., Williamson, R., and Anthony, M. Structural risk minimization over data data-dependent hierarchies. IEEE Transactions on Information Theory, 44: 14:1926-1940, 1998.
Stutz, D., Dvijotham, K. D., Cemgil, A. T., and Doucet, A. Learning optimal conformal classifiers. In International Conference on Learning Representations. arXiv, 2022.
van der Vaart, A. W. and Wellner, J. A. Weak Convergence and Empirical Processes. Springer Series in Statistics. Springer New York, New York, 1996. ISBN 978-1-4757- 2545-2.
Vapnik, V. Principles of risk minimization for learning the- ory. In Neural Information Processing Systems, volume 4.
Curran Associates, Inc., 1991.
Vapnik, V. An overview of statistical learning theory. IEEE Transactions on Neural Networks,
1999.
Vapnik, V. N. and Chervonenkis, A. Ya. On the uniform convergence of relative frequencies of events their probabilities. Theory of Probability & Its Applications, 1971.
Vershynin, High-Dimia Dighe-Dimessional Probability: An Introduc- fion with Applications Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1th edition, 2018. ISBN 978-1-108-4151944, doi: 10.1017/9781099220 108223156.
Vovk, V. Conditional validity of inductive conformal pre- dictors. arXiv preprint arXiv: 1209.2673, pp. 475-490, 2012.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic Learning in Random World. Springer, New York, 2005.
ISBN 978-0-387-00152-- 978-0-387-25661--8
Xi, H., Huang, J., Liu, K., Feng, L., and Wei, H. Does confidence calibration improve conformal prediction? arXiv preprini arXiv: 04344, 2024.
Yang, Y. and Kuchibhotla, A. K. Selection and aggregation of conformal prediction sets. Journal of the American Statistical Association, Online:1-13, 2024.

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
A. Basic Experimental Setup
In this section, we provide a detailed experimental setup. In Appendix A.I, we describe the pre-trained models. In Appendix A.2, we describe the parameter tuning processes for confidence calibration, score function tuning, score aggregation and ConfTr.
A.1. Pre-trained Models
We conduct this empirical study on three image classification benchmarks: CIFAR-I0, CIFAR- 100, and ImageNet. For CIFAR-10. we use a simple CNN consisting of three convolutional layers and two fully connected layers. For CIFAR-100 and ImageNet, we employ ResNet-18 (He et al., 2016). The ImageNet experiments utilize pre-trained classifiers available in Torch Vision (Paszke et al., 2019), while the CIFAR-10 10 and CIFAR- 100 classifiers are trained from scratch using their respective full training sets. For CIFAR-100, the network is trained for 200 epochs using SGD with a momentum of 0.9, a weight decay of 0.0005, and a batch size of 256. The initial learning rate set to 0.1 and decreases by a factor of 5 at epochs 60. 120, and 160. Similarly, for CIFAR-10, the network is trained for 120 epochs using SGD with identical momentum, weight decay, and batch size settings. The initial learning rate also set to 0.1 and decreases by a factor of at epochs 30, 60, and 90.
A.2. Setup for Parameter Tuning
Confidence calibration We investigate two commonly used confidence calibration methods, including temperature scaling and vector scaling (Dabah Tirer, 2024; Guo al.. 2017; Xi et al., 2024). Temperature scaling the simplest extension for Platt scaling (Platt, 1999) and is calibration method that adjusts the model's 's output logits through scalar parameter X. The transformed output probability is defined as a special case of vector scaling with tuning parameter À E IR::
PX (v x:) = v (f)=)
(6)
where f()) is the original logit output from the pre-trained deep classifier model in Section A.I, and by denotes the y-th element of the softmax function:
exp(2;)
(2) = ΣK exp(=x)
for j = -,...,,, K,
where 2 E R K
is the input logit vector and 2j is the j-th component of the input logit vector and (y represents the j-th component of the output probability vector. The vector scaling (Guo et al., 2017) for a logits output of the pre-trained deep classifier model f(x) E Re* with classes K is defined as:
PX
x) v (W f(x) + b),
(8)
where x = TTTT R2K the notation "o" means element-wise product of elements in two vectors. We optimize the parameter À using the objective negative log-likelihood (NLL) to obtain the optimal parameter
PNLL, (A)
1
Σ (D
log(px(y ());
n
where (2 x) is the transformed output probability from temperature scaling or vector scaling. The transformed score
function S*1 (X, y) is a function of p(y| X) based on some base score function, such as APS (Romano et al., 2020) defined
as:
SAPS (x. y.p) = Σ p(ul)=) H(p()( (x) p(y|=)) + u p(y|z)
Y.EY
given probability output : p(y|x) for a classification task, and u is random variable drawn from the uniform distribution U[0, 1]. and THR (Sadinle et al., 2019) defined as:
STuR U.P. = p(y x)).
(10)
Score function tuning Score function tuning is common step in the pipeline of conformal prediction. In this study, we focus on two of the most widely used score functions: RAPS (Angelopoulos et al., 2021) and SAPS (Huang al., 2024):
SsAPs(ær, U.P)) = (L-Pmaxx))) (x),
if oly x; x) = 1,
Pmmx + (o(U.p(>)) - 2 u) Y, else,
12

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
where Pmax (x) is the maximum predicted probability among all classes for input a; o(y, at, xxp) is the order of the true label y in the sorted predicted probabilities p(y]æz), and y is tuning parameter.
A two-stage grid search for parameter searching is performed for both RAPS and SAPS. Initially, the search is conducted over the range [0.01, 0.3] with step size of 0.01 to determine the optimal parameter æ. Subsequently, finer search is carried out within [ar 0.005, x + 0.005] using a granularity of 0.001. Notably, since RAPS is not sensitive to its parameter kregs we focus on 7
Score aggregation Score aggregation could significantly enhance the performance of conformal predictors. Recent studies (Fan et al., 2024; Gasparin & Ramdas, 2024; Ge al., 2024; Luo & Zhou, 2024; Qin et al., 2024; Yang Kuchibhotla, 2024) have proposed aggregation techniques that combine multiple non-conformity scores with tunable weights, which can enhance the efficiency of conformal predictors. These methods typically require hold-out set to search for the optimal weights through grid search. In this study, we investigate the aggregation of three score junctions-APa RAPS, and SAPS-al all derived from the same pre-trained classifier as a case example. Specifically, we use three non-negative parameters w1, W2, and W3, which represent the tunable weights for aggregating the three score functions. These parameters satisfy the constraint W1 + w2 + w3 = 1, and we evaluate all possible value combinations with a granularity of 0.1. The parameters W1, W2, and Wy are restricted to the set {0, 0,,, ..2,....111 We enumerate all triplets (W1, W2, wx) such that:
W1 + W2 w3 1, W1, 22 u3 2 0, and W1, w2, wg E (0....,.22.......
This approach ensures that all feasible combinations of w1, u2, and Wa are comprehensively explored under the given constraint and granularity.
C-Adapter Conformal Adapter (C-Adapter) (Liu et al., 2025) is an adapter- tuming method designed to enhance the efficiency of conformal predictors without sacrificing accuracy. It achieves this by appending an adapter layer to pre-traine pre-trained classifiers for conformal prediction. With C-Adapter, the model tends to produce extremely high non-conformity scores for incorrect labels, thereby improving the efficiency of prediction sets across various coverage rates.
For tuning the C-Adapter, we use the Adam optimizer (Kingma & Ba, 2017) with batch size of 256 and learning rate of 0.1. The model is tuned for 10 epochs, and the only parameter, T, is set to 1 x 10 10-4pp by default. In our empirical study, we explore the application of C-Adapter using hold-out data.
Conformal Training Conformal Training (ConfTr) (Stutz et al., 2022) is a training framework designed to enhance the efficiency of conformal predictors. Its loss function is defined as:
Lcout (f 0), y. 1 Las (f;; + (f 0), 1
soft where Lets represents the classification loss, Liize approximates the size of the prediction set at a coverage rate of 1 - a, To denotes the soft threshold, and À controls the strength of the regularization term. Here, - denotes the soft threshold and A controls the strength of the regularization term. To improve efficiency, ConfTr adjusts the training objective by incorporating a regularization term that minimizes the average prediction set size a specified error rate.
Beyond training models from scratch, ConfTr can also function as post-training adjustment method, allowing fine-tuning of the fully connected layer or appended layer to enhance further the efficiency of conformal predictors (Huang et al., 2023; Stutz et al., 2022). We denote this version of ConfTr ConfTr (ft.). In our empirical study, we explore this application of ConfTr (ft.) using hold-out data. Specifically, we append a fully connected layer to the trained classifier and fine-tune only the parameters of this layer using the Adam optimizer (Kingma & Ba, 2017) with a learning rate of 0.001. The hyperparameter a is set to 0.01 by default. For X, we use a value of 0.0001.
B. Additional Experimental Results
We investigate various conformal prediction algorithms that require parameter tuning. This section provides additional results for these methods. Typically, we vary the size of the calibration set to examine the CovGap. For vector scaling, we consider both the size of the calibration set and the number of parameters (i.c., the amount of frozen weights).
By the results in this section, it is worthy noting that the parameter numbers of those tuning methods (c.g.. VS and C-Adapter) are positively related to the class numbers of the dataset. Thus, datasets with more classes require more parameter numbers
13

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
in the tuning, leading larger tuning bias. This explains why those methods perform differently in various datasets. The details are provided as following.
B.1. Additional Results for Confidence Calibration
Temperature scaling Additional experimental results the tuning bias with temperature scaling are shown in Figures 3a and 3b, using APS and THR the score functions, respectively.
Vector scaling Figure 3c and Figure 3d present additional experimental results on the tuning bias with vector scaling, using THR as the score function. The experiments vary the size of the calibration set and the number of parameters.
The results in Figure 3 show that the tuning bias of temperature scaling is small for all datasets and score functions under various settings. The tuning bias of vector scaling is generally large except for CIFAR-10. For comparison, the tuning bias of temperature scaling is generally smaller than that of vector scaling.
B.2. Additional Results for Score Function Tuning
We focus on two widely used score functions: RAPS and SAPS. The results for them are provided in Figures 4a and 4b. The results in these figures shows the tunig bias of RAPS and SAPS not significantly different from the one with a hold-out set under various settings.
B.3. Additional Results for Score Aggregation
In this study, we investigate the aggregation of three score functions APS, RAPS, and SAPS all derived from the same pre-trained classifier bias of score aggregation is not significantly different from the one with hold-out under various settings.
example. The results provided in Figure 4c. The results in this figure shows the tuning
B.4. Additional Results for C-Adapter
Additional experimental results on CovGap with C-Adapter are shown in Figures 4d and 4e, using APS and THR the score functions, respectively. The results in these figures shows the tuning bias of C-Adapter is not significantly different from the one with a hold-out set under various settings.
B.5. Additional Results for ConfTr (ft.)
Additional experimental results CovGap with ConfTr (ft.) shown in Figures 5a and 5b, using APS and THR the score functions, respectively. The results in these figures shows the tuning bias of ConfTr (ft.) is significantly different from the one with a hold-out set under various settings except CIFAR-10.
C. Additional Results for Regression
We clarify that our analysis reveals a general phenomenon of conformal prediction in both classification and regression tasks. Section focuses classification, as many parameter tuning methods (like TS/VS and ConfTr) designed for classification tasks. Here, we provide the results for regressions to show the case of regression tasks following previous work (Liang et al., 2024) with target coverage of 90% and 30 repetitions. The details are presented as following:
We conduct an empirical study to evaluate methods for constructing prediction intervals using the Conformalized Quantile Regression (CQR) framework. The experiments are performed on the Protein Structure dataset obtained from the UCI repository, which comprises RandomF oreet Quant werpuannieeeggrreeeee LeRegressox instances from Python's quant i ferferest package. The target nominal 0.9.
45730 data points with feature dimension d = 9. The base learners employed are
coverage level for all experiments is set to 1
We investigate two distinct strategies for utilizing the data reserved after model training (referred to calibration set and hold-out set): Same: A single dataset is allocated for both model selection (i.c., choosing the optimal hyperparameter configuration from a set of candidates) and the subsequent calibration step (i.e., determining the empirical quantile required to adjust the prediction interval width): Hold-out: The reserved data is partitioned into two disjoint sets of equal size, where the first set is used for model selection, while the second set is used for calibration, consequently requiring twice the amount
14

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
CIFAR-10
CIFAR-100
ImageNet
same hold-oat
CoyGap (%)
huld-out
CoyGup (%)
1.5
hold-out
1.0
1.0-
Cov
1.0
0.5
0.5
0.5
0.0
0.0
500
1000
1500
2000
2500
1000
2000
3000
4010
Size of Calibration Set
Size of Calibration Set
Size of Calibration Set
(a) Temperature Scaling. APS
CIFAR-10
CIFAR-100
ImageNet
2.0
same
same hold-out
samte
CovGap (%)
hold-out
CoyGap (%)
1.5
hoM-aat
Cov
1.0
0.5
0.5-
2009 2500
500
1000
1500
2000
2500
1000
2000
3000
4000
5000
Size of Calibration Set
Size of Calibration Set
Size of Calibration Set
(b) Temperature Scaling, THR
CIFAR-10
CIFAR-100
ImageNet
2.0
CovGap (%)
hold-out
CovGap (%)
hold out
hold-out
1.5-
CovGap
1.0-
0.5
500
1969
1500
2009
2500
500
1000
1500
2000
2500
6000
7000
8000
9000
10000
Size of Calibration Set
Size of Calibration Set
Size of Calibration Set
(c) Vector Scaling, THR, Size Calibration Set
CIFAR-10
Rouse Stundard
Rease Standard
same
Coverage Gup (%))
Oovrrgoo Cap (%)
CovCap (%)
-
hold-ont
12
14
16
18
20
200
1460
1809
Amounts of Paramters
A Amounts of Parameters
Amountt Parameters
(d) Vector Scaling, THR, Amount of Parameters
Figure 3. Additional results for confidence calibration across various datasets and score functions. The coverage gaps are obtained on the conformal prediction with a hold-out set or the same set as calibration set to parameter tuning. Figures 3a and 3b show the tuning bias with temperature scaling, using APS and THR as the score functions, respectively. The coverage gaps are obtained on the conformal prediction with hold-out set or the same set as calibration set to parameter tuning. Figures 3c and 3d show the tuning bias with vector scaling, using THR as the score function. The experiments vary the size of the calibration set and the number parameters. The experiments are conducted pre-trained models in Appendix A. The coverage rate is set to 0.9. The figure shows that the tuning bias of temperature scaling is small for datasets and score functions under various settings. The tuning bias of vector scaling is generally large except CIFAR- 10. For comparison, the tuning bias of temperature scaling is generally smaller than that of vector scaling.
15

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
CIFAR-10
CIFAR-100
ImageNet
2.0
same buld-out
2.0
same hold-out
same hold-oar
CovGap (%)
CovGap (%)
CovGap (%))
1.5-
1.5
1.0
1.0
0.5
0.5
0.5
0.0
-00
1000
1500
2000
2500
500
1000
1500
2000
2500
1000
2001
2000
4000
5000
Size Calibration Set
Size of Calibration Set
Size of Calibration Set
(a) RAPS
CIFAR-10
CIFAR-100
ImageNet
2.0-
same
2.0
same
1.00
same
CovGap (%)
hold-out
CovGap (%)
hold
CovGap (%)
hold-out
1.5
1.5
0.75
1.-
1.0
0.50
0.5
0.25
0.0
0.00
500
1989
1500
2000
2500
500
1000
1500
2000
2500
1000
2000
3000
4000
5009
Size Calibration
Size of Calibration Sef
Size Calibration Set
(b) SAPS
CIFAR-10
CIFAR-100
ImageNet Net
2.0-
2.0
same
same
CoyGap (%)
1.5
hold-out
CovGap (%)
1.5
hold-oun oold-ouut
CoyGap (%)
1.0
hold-oar
1.0-
1.0
0.5
0.5
0.5
0.0
0.0
500
1989
1500
2000
2500
500
1000
1500
2000
2500
1000
2000
3000
4000
5009
Size Calibration Set
Size of Calibration Set
Size of Calibration Set
(c) Score Aggregation
CIFAR-10
CIFAR-100
ImageNet
2.0
2.0
same
same
>ame
CoyGap (%)
1.5
hold-out
CoyGap (%)
1.5
hold
hold-out
1.0
1.0
1.0
CoyGap
0.5
0.0
0.0
500
1989
1500
2000
2500
500
1000
1500
2000
2500
1000
2000
3000
4000
5000
Size
Calibration
Size of Calibration Set
Size of Calibration Sef
(d) C-Adapter, APS
CIFAR-10
CIFAR-100
ImageNet Net
same
same
same
CovGap (%)
held-out
CovGap (%))
hold-out
CorGap (%))
hold-oar
1.5-
1.5
1.0
L.0-
1.0
0.5
0.5-
0.5
0.0
500
1999
1500
2000
2500
500
1000
1500
2000
2500
1000
2000
3000
4009
5009
Size Calibration
Size of Calibration Set
Size of Calibration Set
(c) Addapter, THR
Figure 4. Additional results for score function tuning, aggregation, and C-Adapter across various datasets and score functions. The coverage gaps are obtained on the conformal prediction with hold-out set the same set as calibration set to parameter tuning. Figures 4a and 4b show the tuning bias with RAPS and SAPS, respectively. Figure 4e shows the tuning bias with score aggregation. Figures 4d and 4c show the tuning bias with C-Adapter, using APS and THR the score functions, respectively. The experiments are conducted on pre-trained models in Appendix A.I. The coverage rate is set to 0.9. The figure shows that the tuning bias of RAPS, SAPS, aggregation, and A-dapteer is not significantly different from the one with a hold-out under various settings.
16

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
CIFAR-10
CIFAR-100
ImageNet
CovGap (%)
2.0
same hold-out
CovGap (%)
10
same hold-oul
CovGap (%)
40-
bold-out
>ame
1.5
1.0
20
0.5-
0-
500
1900
1500
2009
2500
500
1000
1:500
2000
2500
1000
2000
3000
4000
5000
Size
Calibration Set
Size of Culibration Set
Size of Calibration Set
(a) ConfTr(ft.), APS
CIFAR-10
CIFAR-100
Image Net
30-
same
20
same
Coy (%)
hold-ou out
CovGap (%)
hold out
CovGap (%))
60-
same
10-
40-
hold-out
20-
0-
1500 2000
2500
1500 2000
2500
1000
2000
3000
5000
Size of Calibration Set
Size of Calibration Set
Size of Calibration Set
(b) ConfTr(ff)) THR
Figure 5. Additional results for ConfTr(ft.) across various datasets and score functions. The coverage gaps are obtained on the conformal prediction with hold-out set or the same set as calibration set to parameter tuning. Figures 5a and 5h show the tuning bias with ConfTr(ft.), using APS and THR as the score functions, respectively. The experiments are conducted on pre-trained models in Appendix A. The coverage rate is set to 0.9. The figure shows that the tuning hias of ConfTr (ft.) is generally small for all datasets and score functions under various settings.
of reserved data compared to the Shared strategy to achieve an equivalently sized dataset for the final calibration phase. Here we consider the following two experiments:
Experiment Varying the number of candidate models. For the first experiment, the size of calibration set in the Shared strategy is fixed at n 50. For the Shared strategy, these 50 data points are employed for both model selection and calibration, while for the Split strategy, 50 data points are used for model selection, and separate set of 50 data points is used for calibration, amounting to 100 reserved data points in total. The complexity of the model selection task is modeled by varying the number of candidate models. All candidate models are RandomF o orest Quant Qew.unleenngrreeeeeeeeeeeeeeeeee leRegressor instances. The max_features parameter is varied across 10 distinct values, specifically np. Linspace (d/10, d, 10). The n est est imator parameter is adjusted to alter the total pool of models: We vary the number of candidate models by adjusting the n_est imattr or parameter to 4, 8, 12, 16, and 20 values, which combined with the 10 distinct max_features values results in 40, 80, 120, 160, and 200 candidate models respectively.
Experiment 2: Varying the Calibration Set Size In this experiment, the number of candidate models is held constant at 200 (derived from 20 n.estimator values and 10 maxtuea values). We vary the size of the calibration dataset, denoted as n. For the Same strategy, represents the size of the single dataset used for both model selection and calibration, while for the Hold-out strategy, n denotes the size of each of the two datasets (one for selection and one for calibration), resulting in a total reserved data of 2 x n for the Hold-out strategy. The values investigated for both strategies are n E {100, 200, 300, 500).
The results of the two experiments are summarized in Table and Table 3, respectively. Mean Coverage and Std Coverage calculated from the 30 independent runs. The results of the two experiments are similar to the ones in the main text.
D. Some Useful Lemmas and Corollaries
In this section, we provide some useful lemmas and corollaries that are used in the main text. Lemma D.1. (Dvoretzky et al., 1956; Massart, 1990, ShoretzkyKKiefer Peffer-Wolfowit, Inequality) Let I1, D2...., In be independent and identically distributed (i.i...) random variables with common distribution function F. The empirical
17

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Table 2. Results for varying the number of candidate models. For the Same strategy, calibration size 50. For the Hold-out strategy,
n 50 for model selection and n = 50 for calibration. Target coverage - a 0.9.
# Models
Method
Coverage
Length Mean (Std)
Coverage Gap Mean (Std)
Tuning Bias Mean
Mean (Std)
40
Same
0.8437 (0.0383)
12.89 (1.22)
0.0563 (0.0348)
0.0246
Hold-out
0.9251 (0.0268)
17.28 (2.96)
0.0317 (0.0212)
80
Same
0.8229 (0.0354)
12.41 (1.34)
0.0771 (0.0353)
0.0412
Hold-out
0.9049 (0.0404)
16.01 (2.51)
0.0359 (0.0252)
120
Same
0.8258 (0.0564)
12.27 (1.63)
0.0742 (0.0520)
0.0324
Hold-out
0.8953 (0.0480)
15.94 (3.17)
0.0418 (0.0293)
160
Same
0.8373 (0.0467)
12,40 (1.33)
0.0627 (0.0413)
0.0371
Hold-out
0.9163 (0.0286)
16.24 (2.06)
0.0256 (0.0217)
200
Same
0.8447 (0.0494)
12.44 (1.41)
0.0553 (0.0429)
0.0187
Hold-out
0.9037 (0.0406)
15.09 (2.25)
0.0366 (0.0246)
Table 3. Results for varying the calibration set size (n). The number of candidate models is fixed 200. For the Hold-out strategy, refers to size each the two sets (selection and calibration), totaling 2n reserved points, Target coverage
0.9.
Method
Coverage Mean (Std)
Length
Coverage Gap
Tuning Bias
Mean (Std)
Mean (Std)
Mean
100
Same
0.8459 (0.0509)
12.77 (1.25)
0.0541 (0.0433)
0.0150
Hold-out
0.9079 (0.0456)
16.16 (3.11)
0.0391 (0.0278)
200
Same
0.8553 (0.0378)
13.10 (0.96)
0.0448 (0.0337)
0.0118
Hold-out
0.9043 (0.0394)
15.12 (1.72)
0.0330 (0.0212)
300
Same
0.8608 (0.0326)
13.04 (0.93)
0.0392 (0.0296)
0.0158
Hold-out
0.8967 (0.0323)
14.46 (1.04)
0.0234 (0.0192)
400
Same
0.8595 (0.0292)
13.13 (0.56)
0.0405 (0.0266)
0.0157
Hold-out
0.8927 (0.0322)
14.37 (1.16)
0.0248 (0.0201)
500
Same
0.8767 (0.0388)
13.25 (0.68)
0.0327 (0.0269)
0.0037
Hold-out
0.9007 (0.0323)
14.21 (0.65)
0.0290 (0.0189)
18

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
distribution function Fn is defined by
R
(z. = Σ
1(2 - x).
1=1
Then for any > O, the following bound holds:
sup [n(x)) [(x)] >
S -eexp(-nnd
L ERR
Lemma D.2 (Gaussian Tail Inequality). For any a >> O, we have:
e
dt
-
2a
Proof. For any 0, we have:
2
dt
00
e
dt
21e t2
2
a
1
21e =2
dl
20
2a
The inequality in the third line is because when &
0,
:.
Lemma D.3. For score function S* with one one-dimensional parameter space A E, consider the class:
HA (115 5 X R, R).
If (a, y) is continuous, bounded over for any fixed (x, y), then VC(HA) s 2. Specifically, if (x, y) distinct over X y for any fixed then VC(HA) 2.
Proof. We prove that VC(HA) S in two steps:
1. We show that VC(HA) 2 2. Given any two distinct points (æ1, V1) and (I2, y2), we need to verify that all four possible binary labellings (0,0), (0,1), (1,0), (1,1) can be realized by some choice of X and t. Consider S (*x (æ,
For labeling (0,0): Choose f small enough such that both points have values greater than
For labelling (1,1): Choose large enough such that both points have values less than equal to t.
Then forlabellingss (1,0) or (0,1), Since the points are distinct and S* u) is continuous in À over IR, by the intermediate value theorem, there exists some À where (x y1) # (ar2, y2). Then, choose / between these two values.
Therefore, VC(HA) 2 2.
2. We prove that VC(H() < Suppose for contradiction that three distinct points can be shattered. Consider the labelling pattern (1,0,1). This would require some À and such that:
(~1,,, S1 S. (22212)
S ya) 5
implying (*z,, v2) > max (x (1).)))))))))))))))))).)))))(( ,, (x va)}. However, since À is one-dimensional and (ar v) is continu- ous in X, such a complex ordering cannot be achieved at a single À value for all possible three-point configurations. This phenomenon because the continuity of 5 (a. y) over ensures that any crossing of function values must occur in pairs, making impossible to maintain the required ordering consistently. Therefore, three points cannot be shattered, and VC(HA) <
19

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Combining both results, we conclude that VC(HA) 2.
Corollary D.4. For a score function S with parameter space A RR, consider the class:
Hr (1(5 S t AXER .EER)
If Sa,,, y) is continuous and bounded over X for any fixed (æ, v) and (ax, y) is distinct over X x V for any fixed X, then VC(Hx)) 2.
Proof. The proof mirrors Lemma D.3, with À > This restriction does not alter the VC dimension: First, we show that VC(HA)) 2 2. Two points can still achieve all labellings with positive À and Next, we show that VC(HA) S The restriction does not allow shattering three points. Thus, the VC dimension
Lemma D.5. For a score function S with d-dimensional parumeter space IRd, consider the class:
HA (1 S XERS, RJ.
Sx, y) is continuous and bounded over X for any fixed (x, y). then VC(HA) S d+11
Proof. We prove that VC(HA)) - d 1. Suppose for contradiction that d + distinct points can be shattered. Consider any labelling pattern that requires one point to have a value strictly larger than d + 1 other points at the same X. This would require some Ả and such that:
(a 9i) S for E E,, (M))));)
U1) > for some j &
where |4| d + 1. This implies St (z
(5 (z,, v:). However, since À is d-dimensional and S (* y) is continuous in X, such complex ordering requiring one point to dominate d + other points cannot be achieved at single A value. This phenomenon is because the continuity of (* y) over Rd ensures that the ordering relationships between d + 2 points cannot be arbitrary with only degrees of freedom. Therefore, d + 2 points cannot be shattered, and VC(HA) S d +++ 1.
Lemma D.6 (Empirical Process Bound via VC Dimension). For the class HA with finite finte VC dimension VC(HA) Z 1, we have
VC(HA) (CCCH)
ER S SOV
n
where C' is a universal constant.
Proof. is direct result of the VC dimension bound in Vershynin (2018, Theorem 8.3.23).
Lemma D.7. If (x, v) is order-preserving for any transformation X E A. i.e., S^ v) S (x', if and only if 8( < S(x',3' for any transformation X, then for (X, v) with the same distribution as (X,, Vi) E Deat
P(S I E.... Deat) = P(S(x v) S f Deat)
for A E A where i defined in Eq. (2).
Proof. Since 5^ (xx y) is order-preserving for any transformation À E A, we have
S* (^ v) S (>'("')))) and only if S(x,y) S S(x' ./)
for any transformation X. By the definition of İ(>, Dai) and i, the position of 5 (*r, y) among 5* y:) is the same the position of S(x, y) among S(æ,, w1). Then, we have
P(S v) s E(A, Dea) Dea) = P(S((x v) S Deal)
Lemma D.S. For temperature scaling in binary classification, we have pT (y) is order-preserving over (x, y) for any transformation A.
20

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Proof. Noting that
f(z)
( x)) = 4/2
where By is the softmax function defined in Eq. (7). Since
exp (Ju(a:))
(x(
cxp (f((z)) + exp (f1-((z)) 1 exp (f1-v(x) - fv(x))
for binary label y E {0, 1), we have
vy([(x))) S ()(a)))
1 + exp (1- - f,(x)) $ It exp (fi- (1 (x') - fo (x)))
exp ())-(())))) fy(2)) 2 exp (1- (2') - fy(()')
exp (xp((11g((1)) - J5(2:))\\1 2 exp (1/10' (00 - Su (a') (o))))2),, 44 0
1/ (f(z)) i
S/ (f(x')
x
for any transformation À >
E. Proof of Theorem 4.1
Proof. For any sample (z, y) with the same distribution as (zz, (k) E Dea and independent of Deat, recalling the definition of RA. in Theorem 4.1:
RA = sup Σ
(Irest (1,) P ((S (Frest: Vreat) I t Deal)
AEA (E(m)
we have
(S (a, ( P(S $11 S RA.D
7
Then, we have
1 n n 1(S (x,,))) St) RA S ((S St Deal) S
n
Σ
(2,, v1) st) + RA.
(2,,,
n
i=1
Letting = P2 defined Eq. (4) and noting the truth that
(S vi) s S(2, Dai)] [[1 - a1 + n)]
we have
- [11-a)11+1) + m]
[(1 [11- a) + n)]
RA.D S ((S)(a))) S Li Deal) <
+ RAADD.
Take expectations on both sides; we have
CovGap(C, < ERAAD + Ea.n-
21

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
F. Proof of Proposition 4.2
Proof. By Lemma D.I, we have
P(sup - Σ (1S v:) $ - (2, S Dai) > u) S 2exp(-2200) -2mx²). tET
By the property of probability of finite union over A, we have
P sup XEAJET 7
Σ
(2 MA) 5 - P(s St Deai)l u) S 2/A| exp(
i.c.,
P(R > u) 2 -2nx"=
Noting that the bound is too large around 0, we take departure from the bound into two parts from the point v where the probability is just 1. Before this point, the bound is too large, do not use it. Then, the expectation of RA, bounded by two parts:
[og(2|||)
2n
= / P(RAAD. > u) du
E RA
1ox(21A12
2m
P(RAA u) du / LenCgIA
P(RA,, D. u) du
log(2|A[)
2/A| expeexxpxxpe -2mxm) du
2n
log(2|AA)
2|A|
exp(-t²)
2n
V2n
(log(2|A))
log(2|A))
2|A]
1
2n
V2n
2/A /log(2|A))
[2g(2|A|)
1
+
2n
2n (2g(2(AA)
where the second inequality is due to Lemma D.2.
G. Proof of Corollary 4.3 and 4.4
Proof. It is direct application of Proposition 4.2.
H. Proof of Proposition 4.6
Proof. It is direct application of Lemma D.5 and D.6.
I. Proof of Corollary 4.7
Proof. It is direct application of Proposition 4.6.
J. Proof of Proposition 5.1
Proof. We consider a binary classification problem with temperature scaling and THR score applied. The probability
TS (y æ)) is order-preserving of the label for given input for any À E RR, AA E RR+,
px IS (y
x)
P
(v' xx)
= plu x)) - ply x))
(11)
22

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Then, for any two samples (ar, y) and (ar', ,y), with the property of softmax function by on binary classification (see
Lemma D.8 in Appendix D), have
p ( x) S x
plu x)) I plu/ x))
(12)
Then, the direct result is that the order of score function is preserved, i.e.,
STIk (1 V. p\ S STuR(2', Px))
STHR (z S STHR (a', p)).
Therefore, the order of the scores the dataset Deal is preserved for any transformation À R+, iic, the order of S is the same as Sp.,. for any À E RR. Then by Lemma D.7 in Appendix D, we have
P (x, y) $ t (Paa) P (S(z, S ((Dea))
(13)
for any E IR+, which means TuningBias = 0 S Tunssg
K. Order-preserving Regularization and Proof of Proposition 5.2
Order-pres Order-preservine preeerrreeernggeee regularization As discussed in Section 5, applying the regularization on the conformal prediction with confidence calibration or fine-tuning methods could reduce the tuning bias significantly. Taking order-preserving regularization as an example, we modify the class associated with R, as regularization form:
Hx.op = {fx, HA s.t. oly, x. p) = olu, px))
(14)
where o(y, æ, p) the order of the true label y in the sorted predicted probabilities p(-|æ), and ps the probability after confidence calibration like temperature scaling vector scaling. The class HAs.op is constraint version of HA with special regularization. With the constrained ERM with artificial order-preserving regularization, we could obtain a less tuning bias. The tuning bias of the conformal prediction with order-preserving regularization is bounded by the tuning bias of the conformal prediction without order- prder-preserving regularization as Proposition 5.2.
Proof of Proposition 5.2. The ConfTr(op) is regularization case of ConfTr, where the class HA,op is used as the constraint. Since the class H.A.op defined in Eq. (14) is subset of HA, we have
E sup
Σ *E(n]
f(x; vi) (Tress yrea) Deal
S E sup Σ FEHA
f(z;, v:) (Ffes Ihea) Deall
fEHA.
(E(m)
which means that
TuningBias(Coonrrron (op)
TuningBias(Coomrr))
Order-preserving regularization for vector scaling For the vector scaling defined in Eq. (8), because the softmax
function is order-preserving the order-preserving regularization on the output probability Eq. (7) is equivalent to the wnder-preserving regularization on the input logits f(x). If we apply the order-preserving regularization on the vector scaling, we should have for any logits vector f(x),
Vj.j' E [K] (x) S fz( + (zf S Wy by,
where fx())) the j-th element of the logits vector f(x), W, is the j-th element of W, and by the j-th element of b. Lemma K.1. Vector scaling is order-preserving if and only if W, = Wy > for all j.j E [K] and by = by for all j.j E [K].
23

---

Parametric Scaling Law of Tuning Bias in Conformal Prediction
Proof. (+) It is a direct result of the definition of vector scaling.
(+) If vector scaling is order-preserving then
Vj.j' E [K], & fy(()) = W9f(()+ S Wyff(x)) by-
We first exclude the case when W for any j E [K]: For any W and fixed by, we could find small enough fy (x)), such that (x) < (x) and (x) + by
(x) + +by, which contradicts the order-presete preserving property. Therefore, we only consider the case when W, W > 0 for all j.j' E [K]. Without loss of generality, we assume fx) S (x) and W < Wy. and let (x) = fz(z) + e with 2 0, then we have
Wafs(m) + by S W fz (a) + by: = (W; - Wy){s(a)) S by - by + Wyr
Let E - 0, we have
(W, WW-) S by bj
hold for any fz)) We could find a small enough fx). such that
(W, - W }fz (a:) > by bj
This contradicts the order-preserving property. Therefore, we must have Wj- = w > 0 for all j.j" E [K] and by = by for all j.j E [K].
Remark K.2. By Proposition 5.2, if we apply the order-preserving regularization on the vector scaling, the parameter space of the vector scaling is reduced to A = R?.
Dreee-igeg regularization for matrix scaling Here we consider a more complex case that the parameter space of the scaling is matrix: W [a()) + b, where / be a logits value function for a classifier of K classes, and W a matrix of size K K and is vector of size K. Here the dimension of the parameter space K + K. We apply the order-preserving regularization the matrix scaling:
Lemma K.3. Let f be a logits value function for a classification of K classes. The matrix scaling g(x) = Wf(x) + b is onder-preserving if and only W has the form W al + 1v for some scalar a >> 0 and vector E RR and is constant vector (i.e.. by by for all j.j E [K]. Here, I is the K K identity matrix and is the K K-dimensional vector of all ones.
Remark K.4. Here, we regard C-Adapter above proposition shows that the order-preserving regularization reduces the dimension of parameter space from K2 K to K + 2. which is much smaller than VS with its dimension being 2K. Based on the parametric scaling law (Section 4), we explain why C-Adapter can achieve lower tuning bias than VS. And Lemma K. is a special case of Lemma K.3.
special case of matrix scaling with order-preserving regularization. The
L. Additional Theoretical Results of Score aggregation
For more general case about the selection of scores, could also apply the same analysis to the score aggregation (Luo & Zhou, 2024). In the setting of score aggregation, they choose an aggregation weights vector to aggregate multiple score functions:
M
S. (x, 9)
Σ
Wm S, (x, v),
where (w), [ T is the aggregation weights vector. Define the parameter space A as the set of all possible aggregation weights vectors, i.e., A W {w E RRM, EM= Wn = 1, Wm. 2 0}. Then, for grid research, we could also apply Proposition 4.2 to bound its tuning bias to obtain more similar result as Corollary 4.4.
24


Reviews:
[{"review_id": "xzDiaY4qov", "reviewer": "Reviewer_jecM", "summary": "This paper finds out that the coverage gap of using same dataset for tuning and calibration is negligible in most of the conformal prediction methods. Also, this paper observes a scaling law about how parameter space complexity and calibration set size influence the tuning bias. Then this paper proposes a theorectical framework to quantify tuning bias, and gives out a theoretical proof for the scaling law. At the end, this paper discuss two solutions of reducing tuning bias based on the scaling law.", "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": "Thanks for your positive and valuable feedback.\n\n**1. Results of reducing parameter numbers:**\n\nThank you for the suggestion. In the manuscript, we presented two empirical evidences to validate the effect of reducing the parameter number:\n\n1. TS vs. VS (Table 1, Fig. 1 and 3): we present a pilot study to show that TS with fewer parameters achieves much smaller tuning biases than VS with more parameters.\n2. Experiments of scaling law (Fig. 2(a)): we analyzed the correlation between amounts of parameters and tuning bias by freezing different numbers of parameters within VS. The results show that increasing the number of parameters leads to higher tuning bias, supporting the claim.\n\nAs the analysis above is sufficient to show that \"reducing the parameter numbers can result in lower tuning bias\", we did not present more results in Section 5. In the final version, we will explicitly refer to these empirical results in the discussion.\n\n**2. Relation to literature:**\n\nThank you for the positive comment and suggestion. In the final version, we will improve the writing of related work to clearly present the position of this work in the literature. Here, we contextualize our work as follows:\n\n- **Integration with existing theories**: we formulated the tuning bias as *constrained ERM problem*, a special case of learnability theory (we discussed in related work). In Subsec. 4.2 and 4.3, we introduce *Dvoretzky–Kiefer–Wolfowitz inequality* and *VC dimension* to analyze the tuning bias in finite and infinite parameter spaces, respectively. Thus, our theoretical framework is tightly integrated with existing machine learning theories, as discussed in related work.\n- **How it benefits future works**: In this work, we provide the first study to quantify the tuning bias and its scaling laws. This enables researchers to determine when splitting the dataset is necessary or if data reuse is acceptable, which is particularly crucial in data-scarce scenarios (such as rare diseases in medical diagnosis). In addition, we also provide practical guidelines for developers to alleviate the tuning bias (as appreciated by Reviewer 4yEA). Theoretically, this work is the first to employ the ERM framework in conformal prediction, offering a novel tool for analyzing the learnability of general conformal prediction problems.\n\n**3. The practical necessity of exploring tuning bias and why not split dataset**\n\nThank you for highlighting this writing issue. In the current version, we only describe the significance of reducing tuning bias in the discussion (Sec. 5), which makes it challenging for readers to grasp the motivation earlier in the paper. Here, we'd like to clarify that understanding the tuning bias is crucial in conformal prediction practice: \n\n- **Data-scarce scenarios**: Splitting the labeled dataset is impractical in data-scarce scenarios like rare diseases, natural disaster prediction, and privacy-constrained personal data. With limited data, using separated datasets will reduce points for parameter tuning and conformal calibration, compromising the approach's effectiveness and stability. Thus, it’s valuable to assess when splitting is needed, or data reuse is permissible rather than sticking to traditional practices.\n- **Simple implementation**: Even with sufficient data, maintaining separate sets can increase the pipeline complexity. Understanding when this separation is unnecessary—such as when tuning bias is negligible—enables simpler, more streamlined workflows while preserving coverage guarantees, offering practical relevance.\n- **Foundational understanding**: exploring the tuning bias can provide an in-depthknowledgeg of the exchangeability assumption in conformal prediction. In particular, the insight in this work may inspire future works in non-exchangeable conformal prediction. \n\nIt could also answer Reviewer jaH5's concern, \"why not split split the dataset?\" for the same reasons.  Indeed, it is easy to split the validation set when the provided data is sufficient. However, it can be particularly important to consider data reusing in data-scarce scenarios, like rare diseases, natural disaster prediction, and privacy-constrained personal data. With limited data, separating the dataset will further exacerbate the data scarcity problem, compromising the effectiveness of both conformal calibration and parameter tuning. In addition, exploring the tuning bias can provide an in-depth understanding of the exchangeability assumption, which may inspire future works in non-exchangeable CP. \n\nAs suggested by the reviewer, we will emphasize the motivation of exploring the tuning bias in the Introduction and Background of the final version.\n\n**4. Supplementary material and notation**\n\nThanks for the suggestion. In the final version, we will update the notation of TuningBias and CovGap with text form and release the code on GitHub once it is accepted.", "claims_and_evidence": "The claims are clear, and the evidence is convincing.", "methods_and_evaluation_criteria": "For the methods, there is a risk of overfitting to the specific characteristics of the calibration data used in the study, particularly if the separation between tuning and calibration is not well-managed. This could lead to models that perform well on specific dataset characteristics but poorly generalize to new data, undermining the reliability and utility of the predictions in practical applications. These drawbacks underscore the need for careful application and further testing of these methods across various settings and conditions to fully understand their limitations and potential.", "theoretical_claims": "The theoretical claims are solid with proofs.", "experimental_designs_or_analyses": "Although the paper discusses how tuning bias scales with the complexity of the parameter space, there might be a lack of experiemental results that can show how reducing the number of parameter could help reducing the bias.", "relation_to_broader_scientific_literature": "While the paper contributes interesting findings on tuning bias and its scaling laws, it may not adequately integrate these contributions with existing theories or frameworks within the broader field of machine learning. Even in the field of conformal prediction, how the findings help the further research path is not mentioned.", "essential_references_not_discussed": "All the essential references are discussed.", "other_strengths_and_weaknesses": "I think this paper is not well-motivated, the paper may not sufficiently demonstrate the practical necessity of investigating tuning bias where the tuning and calibration datasets are the same. In most real-world applications and existing research, these datasets are intentionally kept separate to avoid overfitting and ensure the model's generalizability. The necessity to study what happens when they overlap might not be convincingly argued, making the motivation behind this research seem theoretical rather than practical. If the paper leans heavily on theoretical justifications without clear paths to application or examples of real-world scenarios where such tuning bias issues prominently occur, it might reinforce the impression that the motivation is more academic than practical.", "other_comments_or_suggestions": "There are not too much typos or notation error, but I recommend to make the TuningBias and CovGap in the formula as Text form.", "questions_for_authors": "No questions.", "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": "osp6WZ0ggV", "reviewer": "Reviewer_mAZq", "summary": "This paper points out the problem that the exchangeability assumption of conformal prediction does not hold if the holdout set (applied for parameter tuning) and calibration set are identical. A parametric scaling law is proposed such that the tunning bias increases with parameter space complexity and decreases with calibration set size. A theoretical study is conducted to provide an upper bound of the bias. Potential solutions, like regularization during tunning, are provided.", "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 the reviewer for the nuanced and constructive feedback. Below, we address your concerns point by point.\n\n**1. Lack of a sophisticated solution**\n\nWe want to clarify that the primary objective of this work is to provide a comprehensive understanding of tuning bias in conformal prediction rather than to develop a specific, sophisticated solution at this stage. To this end, we present the main contributions of this study as follows: identifying the tuning bias, introducing a scaling law for the tuning bias, and establishing a theoretical framework to quantify its upper bound. Furthermore, we discuss potential solutions for mitigating tuning bias as an extension. Rather than introducing a novel methodology, we propose **two effective guidelines** to address tuning bias in real-world applications: reducing the parameters of model tuning (e.g., adopting a more parameter-efficient strategy) and implementing regularization techniques (e.g., order-preserving constraint). These guidelines provide **actionable**, **theory-driven** solutions and establish a foundation for future research to develop specialized methods tackling this challenge. Therefore, we believe this work not only **builds a robust theoretical framework** for understanding tuning bias—as recognized by Reviewer jaH5—but also **charts a clear path** for subsequent studies in this field.\n\n**2. Task scope**\n\nThank you for the suggestion. We clarify that our analysis reveals a general phenomenon of conformal prediction in both classification and regression tasks. Section 3 focuses on classification, as many parameter tuning methods (like TS/VS and ConfTr) are designed for classification tasks. Here, we provide new results to show the case of regression tasks following previous work [1] with a target coverage of 90% and 30 repetitions. We present the CovGap and TuningBias (in percentage) in the table below:\n\n|Method|Varying #models||Varying Cal. Size||\n|-|-|-|-|-|\n||40|160|100|500|\n|Same|5.63|6.27|5.41|3.27|\n|Hold-out|3.17|2.56|3.91|2.90|\n|**Tuning-bias**|2.46|3.71|1.50|0.37|\n\nFrom the table above, we validate the parametric scaling law of tuning bias on regression tasks. In addition, our theoretical framework is general for various tasks. We will clarify the task scope and add the above results and details of the experiments in the final version.\n\n**3. Table 1 - Standard deviations/repeats**\n\nThanks for the suggestion. In the current version, we present average results with few runs in Table 1. Here, we updated the results (in percentage) with 30 runs:\n\n| Method | CIFAR-100 | ImageNet |\n|-|-|-|\n|TS| **0.59 ± 0.38** | **0.43 ± 0.29** |\n|VS| 1.63 ± 0.76 | 6.43 ± 0.53 |\n| ConfTr (ft.) w/ OP | **0.52 ± 0.37** | **0.40 ± 0.31** |\n| ConfTr (ft.) w/o OP | 6.15 ± 0.86 | 21.68 ± 0.58 |\n\nThe new results lead to the same conclusion as the previous version. We will update the table in the final version.\n\n**4. Performance gap between various datasets**\n\nThank you for the suggestion. It is wothy noting that the parameter numbers of those tuning methods (e.g., VS and C-Adapter) are positively related to the class numbers of the dataset (See Line 354). Thus, datasets with more classes require more parameter numbers in the tuning, leading to a larger tuning bias. This explains why those methods perform differently in various datasets. We will add a brief explanation in Appendix B of final version.\n\n**5. Concerns of presentation**\n\nThank you for raising the writing concerns. We agree that a clearer and more consistent notation system can benefit the paper a lot: \n1. **CovGap**: Both CovGap and TuningBias are dataset(distribution)-level metrics, instead of instance-level. In particular, CovGap measures the absolute difference between the target coverage and the actual coverage on the dataset/distribution, see Line 81. In addition, CovGap is a function of alpha, but we omit the alpha for simplicity. We will fix the notation issue in Lines 80-81 and update the notation to ensure consistency in the final version.\n2. **Prediction set**: $\\hat{C}$ in Eq. (3) and (5) are the empirical form of the CP set, where the *hat* notation emphasizes it is associated with observations. $C$ denotes general form CP sets that may be assigned without observations (e.g., oracle CP sets). \n3. **Clarify $\\mathcal{R}_\\Lambda$**: It is the supremum of an empirical process. In the current version, we define it in Line 239 and rewrite it in Line 260.  The  $E\\mathcal{R}_\\Lambda$ is expected over the distribution of the calibration set. \n4. **Propositions**: Prop. 5.1 and 5.2 are theoretical derivations (See proofs in App. I and J) instead of empirical observations. \n5. Other issues: we will add proper citations, fix the typos, and improve the clarity in the final version. Thank you again for the nuanced review. \n\n[1] Liang, Ruiting, Wanrong Zhu, and Rina Foygel Barber. “Conformal Prediction after Efficiency-Oriented Model Selection.” arXiv. https://doi.org/10.48550/arXiv.2408.07066. (2024)", "claims_and_evidence": "Claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "This work does not propose an implementable solution (i.e. an algorithm). Only an intuitive solution is provided.\n\nThe notation of a prediction set is not consistent. It shows up \\hat{C} and C in different places. Do they refer to different concepts?\n\nThe metric CovGap is introduced clearly. In line 80, as prediction set C(x) is related to the test input x. However, CovGap(C) is only a function of C and x disappears. Do you mean CovGap is the expectation of coverage gap for all test inputs? The same problem happens to other metric definitions, including TuningBias(C). \n\nThe empirical study is conducted on APS score, but the score is not cited in line 163 until Appendix A.", "theoretical_claims": "Based on Eq.(2), a ceiling function should be added at the subscript of Q in Eq.(4).\nThe upper bound \\mathbb{E}\\mathcal{R}_\\Lambda is not introduced clearly when it shows up first in line 232 until line 260. Also, it is not clarified what space/set the expectation is calculated on.", "experimental_designs_or_analyses": "Experiments are only conducted on two datasets CIFAR-100 and ImageNet, and there is no regression task. It should be claimed if the work only focuses on conformal prediction on classification tasks. There is no standard deviation results in Table 1. The authors do not mention the experiments in Table 1 were conducted multiple times.", "relation_to_broader_scientific_literature": "The problem of overfitting the holdout set, which should not be applied for calibration, is kind of novel, and I appreciate the experimental and theoretical works. The goal of reducing the amount of parameters and regularization is to prevent the overfitting issue. People can easily come up with the ideas without the theoretical analysis. More sophisticated solutions are expected for higher impact.", "essential_references_not_discussed": "The related works are introduced extensively.", "other_strengths_and_weaknesses": "The investigated problem is novel and sufficient theoretical works are conducted. \n\nHowever, the presentation should be further improved. For instance, the same notations are reused for different concepts, such as \\hat{C} in Eq.(3) and Eq.(5).  Legends for 'same' and 'holdout' are not consistent in figure 2 and 3. Writing should be improved. In line 367, 'Theoretically. we provide a theoretical result...'. The poor presentation makes the paper hard to understand. It hinders me to validate the correctness of some theories and proofs.\n\nBesides, as mentioned above, the works lacks a more insightful solution to the problem. The experiments of the current intuitive solutions are not enough either.", "other_comments_or_suggestions": "There is a typo in line 246. The notation system should be redesigned. Also, the name of corollary and proposition is abused. Intermediate conclusions or experiment observations should not be stated as corollaries and propositions (such as proposition 5.1 and 5.2).", "questions_for_authors": "What space of \\mathbb{E}\\mathcal{R}_\\Lambda is computed over?\nCovGap is a function of alpha in line 233. Does CovGap is also a function of alpha in line 81 as well?", "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": "VPzXcqJ50P", "reviewer": "Reviewer_4yEA", "summary": "In this paper, the authors focus on the tuning bias produced by parameter tuning in many conformal preidction methods. First, they  reveal that the tuning bias is negligible for simple parameter tuning in many conformal prediction methods. Then, the authors establish a parametric scaling law, showing that tuning bias increases with parameter space complexity and decreases with calibration set size, supported by both empirical evidence and a theoretical framework using constrained ERM and VC dimension. The paper also discusses solutions to mitigate tuning bias, such as increasing the calibration set size or reducing parameter space complexity through fewer parameters or regularization techniques.", "questions": "", "limitations": "", "rating": 5, "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 the reviewer for the positive feedback. Below, we address your concerns point by point.\n\n**1. C-Adapter vs. Vector Scaling**\n\n> Please explain why C-adapter achieves much smaller tuning bias but vector scaling cannot? It seems C-adapter tunes more parameters than VS.\n\n\nThank you for the insightful question. It prompted us to delve deeper into the structural differences between C-Adapter and Vector Scaling (VS). In particular, we find that the **order-preserving regularization** in C-Adapter can significantly decrease the tuning bias. Formally, we propose a new proposition:\n\n**Proposition:** *Let $f$ be a logits value function for a classification of $K$ classes. The matrix scaling $g(x) = W f(x) + b$ is order-preserving if and only if $W$ has the form $W = a I + \\mathbf{1} v^T$ for some scalar $a > 0$ and vector $v \\in \\mathbb{R}^K$, and $b$ is a constant vector (i.e., $b_j = b_{j'}$ for all $j, j'\\in [K]$). Here, $I$ is the $K \\times K$ identity matrix and $\\mathbf{1}$ is the $K$-dimensional vector of all ones.*\n\nHere, we regard C-Adapter as a special case of matrix scaling with order-preserving regularization. The above proposition shows that **the order-preserving regularization reduces the dimension of parameter space from $K^2 +K$ to $K+2$**, which is much smaller than VS  with its dimension being $2K$. Based on the parametric scaling law (Section 3), we explain why C-Adapter can achieve lower tuning bias than VS. Thank you again for inspiring us to revealing the impact of order-preserving regularization and we will add it in the discussion of the final version.\n\n**2. Experimental details & reproducibility**\n\n> The experimental designs and analyses ... can be benefited if the authors can provide more detailed information on hyperparameter settings, such as the number of repetitions. I believe it would improve the reproducibility and robustness of the findings.\n\nThank you for the suggestion. We provide the experimental settings in Appendix A. In particular, we repeat all experiments with 30 runs and present the standard deviations in Fig. 2. In the final version, we will improve the writing of experimental setup to enhance the clarity and reproducibility.\n\n**3. Writing clarity (subsections 3.1/3.2)**\n> (Minor issue) The writing of experimental results is a little ambiguous. I encourage the authors to improve the writing of Subsections 3.1 and 3.2, providing more details of the experimental settings and clearer observations.\n\nThank you for pointing out the writing issue. We will revise Subsections 3.1 and 3.2 to clearly present the experimental settings and the key observations, in the final version.", "claims_and_evidence": "The claims made in the submission are generally supported by clear and convincing evidence, including a combination of empirical results, theoretical analysis, and practical considerations.", "methods_and_evaluation_criteria": "The evaluation criteria make sense for the problem of tuning bias in conformal prediction. The paper conducts extensive empirical studies across various conformal prediction methods (e.g., RAPS, SAPS, score aggregation, temperature scaling, vector scaling, C-Adapter, ConfTr) on benchmark datasets such as CIFAR-10, CIFAR-100, and ImageNet. These datasets are standard in machine learning and are suitable for evaluating the performance of conformal prediction methods. By varying the calibration set size and the complexity of the parameter space, the paper effectively demonstrates the impact of these factors on tuning bias, which aligns with the theoretical analysis.", "theoretical_claims": "The theoretical claims are supported by correct and logically sound proofs, grounded in established statistical learning theory. For example, the derivation of the scaling law is supported by Proposition 4.2 and Proposition 4.6, which provide bounds for the tuning bias in finite and infinite parameter spaces, respectively. These propositions use classical concentration inequalities and VC dimension bounds. While the proofs could benefit from more detail and rigor in certain steps, the overall correctness of the theoretical analysis is robust.", "experimental_designs_or_analyses": "The experimental designs and analyses in the paper are generally sound and valid. This work can be benefited if the authors can provide more detailed information on hyperparameter settings, such as the number of repetitions. I believe it would improve the reproducibility and robustness of the findings.", "relation_to_broader_scientific_literature": "In summary, the paper makes several key contributions that advance the understanding of tuning bias in conformal prediction, both theoretically and empirically. In particular, this work provides new insights and practical guidelines for managing tuning bias in real-world applications:\n1. Analyzing the Tuning Bias in Conformal Prediction;\n2. Presenting Parametric Scaling Law of Tuning Bias;\n3. Theoretical Framework to quantify the upper bound;\n4. Practical Guidelines to reduce tuning bias.\n\nAlthough some works investigated the non-exchangeability of using the same dataset(as stated in the Introduction), this work is novel as it provides a extensive study on quantifying the tuning bias of conformal prediction, which could be pretty interesting in the community.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths\n1. The problem studied in this paper is significant. It is practical to use the same hold-out data for conformal calibration and parameter tuning in data-scarce scenerios. Therefore, the findings have practical implications for improving the reliability of conformal prediction in real-world applications.\n2. The theoretical analysis is solid. The paper’s theoretical framework offers a new perspective on tuning bias, which could influence future research in statistical learning and uncertainty quantification.\n3. The paper is well-structured, with clear delineation between empirical studies, theoretical analysis, and practical solutions\n4. The proposed guideline is useful. The discussion of potential solutions to mitigate tuning bias, such as increasing the calibration set size and reducing parameter space complexity through regularization, provides actionable insights for practitioners.\n\n\nWeaknesses\n1. (Minor issue) The writing of experimental results is a little ambiguous. I encourage the authors to improve the writing of Subsections 3.1 and 3.2, providing more details of the experimental settings and clearer observations.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please explain why C-adapter achieves much smaller tuning bias but vector scaling cannot? It seems C-adapter tunes more parameters than VS.", "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": "2n8fbuggm3", "reviewer": "Reviewer_jaH5", "summary": "The manuscript explores the phenomenon of tuning bias in the field of conformal prediction, which is a statistical method used to ensure that prediction intervals or sets cover the true value with a specified probability. The focus is on how the tuning of parameters, when done on the same dataset used for calibration, affects the coverage accuracy of the prediction models. Key points from the paper include:\n\n1.\tTuning Bias Definition and Impact: Tuning bias is defined as the coverage gap that arises when the same data set is used for both parameter tuning and calibration. The paper empirically demonstrates that this bias is generally negligible for simple parameter tuning across various conformal prediction methods.\n\n2.\tParametric Scaling Law: The study observes that the magnitude of tuning bias increases with the complexity of the parameter space and decreases with the size of the calibration set. This relationship is formalized through the derivation of upper bounds on the tuning bias, which align with empirical observations.\n\n3.\tTheoretical Framework: A theoretical framework is established to quantify the tuning bias, using empirical process theory within the extended parameter space. This framework provides a rigorous basis for understanding and predicting the behavior of tuning bias under different conditions.\n\n4.\tEmpirical Studies: The paper includes extensive empirical evaluations involving methods like RAPS, SAPS, score aggregation, and confidence calibration methods, using datasets like CIFAR-100 and applying models like ResNet-18. These studies confirm the scaling laws and the minimal impact of tuning bias under typical conditions.\n\n5.\tReduction Strategies: Potential strategies to mitigate tuning bias are discussed, focusing on increasing calibration set size or reducing parameter space complexity. Practical challenges such as data scarcity are acknowledged, suggesting order-preserving regularization as a promising approach to manage tuning bias effectively.\n\n6.\tContributions and Future Directions: The primary contributions are identifying the negligible effect of tuning bias in many scenarios, formalizing the parametric scaling law of tuning bias, and proposing theoretical models to understand and predict tuning bias. The paper suggests further research could explore structured parameter spaces to refine the precision of tuning bias predictions.\n\nOverall, this paper provides a significant theoretical and empirical foundation for understanding tuning bias in conformal prediction, offering insights that can help in designing more reliable machine learning models, particularly in settings where rigorous uncertainty quantification is critical.", "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": "Thanks for your positive review and insightful feedback.\n\n**1. Exchangeability definition/discussion**\n\nThank you for the suggestion. We agree that introducing the exact definition earlier can improve the clarity. In the current version, we defaultly introduce Exchangeability as a well-known assumption of CP (with references). In the final version, we will add the exact definition of Exchangeability in Sec. 2, as the reviewer suggested. We present in Subsec. 4.1 (Lines 261-274) why using the same dataset violates the Exchangeability. We will improve the clarity of this part in the final version.\n\n**2. Clarification of the term \"scaling law\"**\n\nThank you for raising the concern. Recently, the term \"scaling law\" frequently appears in the context of large language models - the performance scales up with parameter/data numbers. We want to clarify that the above scaling law is formally termed \"neural scaling law\" (see Wikipedia), a special case of empirical scaling law. Notably, the term 'scaling law' in deep learning refers to a broader concept that describes the relationships between functional properties of interest (such as tuning bias in our work) and characteristics of the model architecture or dataset (e.g., model size) [1]. To improve the clarity, we will add a concise description of \"scaling law\" with references in the final version.\n\n**3. Seemingly conflicting claims**\n\nThank you for highlighting the potential misunderstanding. We want to clarify that 'simple parameter tuning' in the first claim refers to methods with few parameters, such as RAPS and TS. As Line 135, we excluded methods with a larger number of parameters, such as VS and the fine-tuned version of ConfTr. We use the first claim to demonstrate that tuning bias can be negligible in certain cases, which motivates the subsequent analysis. This does *not* conflict with the second claim regarding the parametric scaling law, which illustrates when tuning bias can be either small or large. To enhance clarity, we will revise the first claim to state: 'The tuning bias is not always significant for parameter tuning in ...'\n\n**4. Concerns on CovGap**\n\nCovGap is computed empirically as the absolute difference between the target coverage ($1-\\alpha$) and the empirical coverage:\n$$\n|(1-\\alpha) - \\frac{1}{n'} \\sum_{i=1}^{n'} \\mathbb{1}(y_i \\in \\hat{C}(x_i))|,\n$$\nwhere $n'$ is the size of the test set, and $ \\hat{C}(x) $ is the CP set for an input $x$. We will add a concise description of CovGap in the final version. As for the method, we present potential solutions for mitigating tuning bias as an extension (See response #1 to reviewer mAZq). We hope the guideline can inspire more future work to design specific methods for addressing this challenge. \n\n**5. Theoretical contribution and uniqueness**\n\nThank you for the recognition. In this work, we formulate the tuning bias into ERM framework, and propose a general theory to bound the tuning bias by the PAC and empirical process theories, explaining the empirical scaling law. Then, we derive the bias bounds in finite and infinite parameter cases, respectively. In particular, we also provide the specific bounds of tuning bias in various tuning methods. Lastly, we provide the theoretical results to support the two practical guidelines addressing the challenge. We list the theoretical contribution as follows:\n\n1. **Problem formulation**: This work is the first to formulate the \"tuning bias\" arising from dataset reuse, which provides a new direction for understanding non-exchangeable CP.\n2. **CP-specific complexity analysis**: We derive the bounds of tuning bias with the complexity measures (e.g., VC dimension) of the *CP-specific hypothesis class*, which can be developed as a theoretical toolkit for refined bounds of general biases in CP.\n3. **Analytical framework for tuning methods**: we establish a framework to derive the bias bounds for various tuning methods and present several examples. This framework can be utilized as a theoretical justification for special-designed methods in subsequent works.\n\n**6. Why not choose other methods?**\n\nThank you for the insightful question. As Sec. 5, we mitigate the tuning bias by reducing the number of parameters. A specific example is to use alternative methods with fewer parameters (e.g., switching from VS to TS). However, this way may be impractical when complex methods are necessary to obtain tighter CP sets (ConfTr), improved model calibration (VS), and so on. This question highlights our contribution to revealing the scaling law of tuning bias, which provides guidelines for designing the tuning process in various scenarios.\n\n**7. Why not split the dataset?**\n\nThank you for raising the concern. We refer to reviewer jecM's response #3 to answer the issue. As suggested by the reviewer, we will strengthen the motivation in Sec. 2 of the final version. \n\n[1] Villalobos, Pablo. \"Scaling Laws Literature Review.\" Published online at Epochai. org (2023).", "claims_and_evidence": "The exact definition of exchangeability appears very late in the paper, which can be formalized, highlighted a bit of earlier. Also, a clearer discussion on the relationship between exchangeability and the using of the same dataset for tuning and calibration can be further highlighted. \n\nI am not sure if I am correct, but for many of previous works, it seems that scaling law typically indicates larger parametric space / data scales leads to improve performance or robustness. However, in this paper, the authors seems to understand the problem of conformal prediction from a generalization perspective, exploring the impacts of parameter space and data scales, which is quite a style of classical machine learning. So, I am concerned if the “Scaling Law” can be somewhat misleading in the title. \n\nI am quite confusing about two seemingly conflicting claims: “the tuning bias is negligible for simple parameter tuning in conformal prediction methods” and “the parametric scaling law of the tuning bias increases with parameter space complexity and decreases with calibration set size”. From my understanding, the former states that the violation of exchangeability is not actually a big deal yet latter states that it is still have side impacts, especially influenced by the data scale and parameter scale. Hoping the authors could made some clarification to address my misunderstandings.", "methods_and_evaluation_criteria": "I think the authors could further clarify how the CovGap is computed in practice, which seems critical for their empirical analyses.  Also, for the potential solutions section, the mentioned methods are quite easy. However, for a theoretical style paper, maybe it is not a big deal.", "theoretical_claims": "I think the authors would like to take their works as a theoretical style paper, which is evident from its large amount of discussions on theoretical analysis and small amount of experimental verification. \n\nI did not check every details within the theoretical analysis, but it seems like an applications of PAC framework for CP problem, where the dataset size is echoed by n and the parameter space is echoed by VC dimension. I may raise two questions, 1) what’s the challenges, uniqueness, and contributions of this work from a theoretical perspective, as I think this paper should be categorized as a theoretical analysis work. 2) Besides echoing the observations within Section 3, what other observations can we draw from the new theoretical analysis.", "experimental_designs_or_analyses": "From Figure 1, it seems that the CovGap values are small except for VS and ConfTr ft. Therefore, why do not we just choose other CP methods or are their some particular interesting in using those methods with more hyper-parameters like VS and ConfTr?", "relation_to_broader_scientific_literature": "This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which I feel must be specifically highlighted.", "essential_references_not_discussed": "The authors fully review the existing literature with many concrete examples, therefore I think the reference is good enough.", "other_strengths_and_weaknesses": "It seems that the authors consider the situation where the same dataset is used for tuning and calibration, aiming to understanding its impacts on tuning bias. However, I am concerned that if it is truly difficult to have another hold-out set, as the validation dataset can be easily separated into two parts, one for tuning and one for calibration. I think the authors could further emphasize why the considered setup is pragmatic or this problem has some other interesting factors from an academic point of view.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please see the comments above.", "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: This paper tracks an important problem: conformal prediction which is a popular framework of uncertainty quantification that constructs prediction sets with coverage guarantees. The authors establish a theoretical framework to quantify the tuning bias and provide rigorous proof for the scaling law of the tuning bias by deriving its upper bound. 

In the initial reviews, reviewers have some concerns regarding the presentation of this paper and request some clarifications. After the rebuttal, all reviewers agree that this paper should be accepted due to its novelty.

The authors are encouraged to merge all comments to further improve the presentation quality of this paper. I nominate this paper for oral presentation due to the significance of the researched topic.
Decision: Accept (poster)