Parametric Scaling Law of Tuning Bias in Conformal Prediction

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.

Machine learning methods like conformal prediction promise reliable uncertainty estimates, but many require an additional dataset for tuning parameters, which is costly when data is limited. Reusing the same data for tuning and calibration can create a "tuning bias," potentially compromising these reliability guarantees. Our research investigated this tuning bias, revealing empirically that it is often negligible for simple parameter tuning. We discovered a "parametric scaling law": this bias increases as the complexity of the tuning process (e.g., more parameters) grows, but decreases as the size of the calibration dataset increases. We then established a theoretical framework to quantify this tuning bias and rigorously prove its scaling behavior. This work is crucial for data-scarce applications, offering insights into when reusing data is permissible and guiding the design of more data-efficient and trustworthy AI systems without needing an extra hold-out set.