Parametric Scaling Law of Tuning Bias in Conformal Prediction

Thanks for your positive review and insightful feedback.

1. Exchangeability definition/discussion

Thank 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.

2. Clarification of the term "scaling law"

Thank 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.

3. Seemingly conflicting claims

Thank 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 ...'

4. Concerns on CovGap

CovGap is computed empirically as the absolute difference between the target coverage ($1-\alpha$) and the empirical coverage:

$$|(1-\alpha) - \frac{1}{n'} \sum_{i=1}^{n'} \mathbb{1}(y_i \in \hat{C}(x_i))|,$$

where $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.

5. Theoretical contribution and uniqueness

Thank 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:

1. 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.
2. 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.
3. 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.

6. Why not choose other methods?

Thank 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.

7. Why not split the dataset?

Thank 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.

[1] Villalobos, Pablo. "Scaling Laws Literature Review." Published online at Epochai. org (2023).

We thank the reviewer for the positive feedback. Below, we address your concerns point by point.

1. C-Adapter vs. Vector Scaling

Please explain why C-adapter achieves much smaller tuning bias but vector scaling cannot? It seems C-adapter tunes more parameters than VS.

Thank 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:

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.

Here, 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.

2. Experimental details & reproducibility

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.

Thank 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.

3. Writing clarity (subsections 3.1/3.2)

(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.

Thank 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.

We thank the reviewer for the nuanced and constructive feedback. Below, we address your concerns point by point.

1. Lack of a sophisticated solution

We 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.

2. Task scope

Thank 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:

From 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.

3. Table 1 - Standard deviations/repeats

Thanks 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:

The new results lead to the same conclusion as the previous version. We will update the table in the final version.

4. Performance gap between various datasets

Thank 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.

5. Concerns of presentation

Thank you for raising the writing concerns. We agree that a clearer and more consistent notation system can benefit the paper a lot:

1. 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.
2. 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).
3. 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.
4. Propositions: Prop. 5.1 and 5.2 are theoretical derivations (See proofs in App. I and J) instead of empirical observations.
5. 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.

[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)

Thanks for your positive and valuable feedback.

1. Results of reducing parameter numbers:

Thank you for the suggestion. In the manuscript, we presented two empirical evidences to validate the effect of reducing the parameter number:

1. 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.
2. 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.

As 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.

2. Relation to literature:

Thank 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:

• 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.
• 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.

3. The practical necessity of exploring tuning bias and why not split dataset

Thank 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:

• 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.
• 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.
• 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.

It 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.

As suggested by the reviewer, we will emphasize the motivation of exploring the tuning bias in the Introduction and Background of the final version.

4. Supplementary material and notation

Thanks 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.