Title: Fundamental limits on the efficiency-confidence trade-off in transductive conformal prediction

Abstract: Transductive conformal prediction is designed to handle the simultaneous forecasting of multiple data points. The primary goal, given a specific confidence level, is to generate prediction sets that capture the true outcomes with the specified reliability. This study establishes a fundamental trade-off between confidence and efficiency within transductive frameworks, where efficiency is quantified by the magnitude of the prediction sets. We derive a rigorous finite-sample bound demonstrating that achieving any non-trivial confidence level results in an exponential increase in the size of prediction sets for data exhibiting inherent uncertainty. The exponent in this growth is linearly dependent on the sample size and proportional to the data’s conditional entropy. Furthermore, the bound incorporates a second-order component known as dispersion, which represents the variance of the log conditional probability distribution. We prove that transductive methods utilizing an approximate conditional distribution are capable of approaching this theoretical limit. Leveraging these insights, we propose a practical transductive prediction algorithm that outperforms traditional Bonferroni-based approaches.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC