Fundamental bounds on efficiency-confidence trade-off for transductive conformal prediction
This work addresses a fundamental limitation in uncertainty quantification for machine learning, providing theoretical bounds that impact methods relying on transductive prediction, though it is incremental in refining existing theoretical frameworks.
The paper tackles the trade-off between confidence and efficiency in transductive conformal prediction, deriving a strict finite-sample bound that shows exponential growth in prediction set size with non-trivial confidence levels, scaling linearly with sample number and proportional to conditional entropy, and demonstrates achievability in an idealized setting.
Transductive conformal prediction addresses the simultaneous prediction for multiple data points. Given a desired confidence level, the objective is to construct a prediction set that includes the true outcomes with the prescribed confidence. We demonstrate a fundamental trade-off between confidence and efficiency in transductive methods, where efficiency is measured by the size of the prediction sets. Specifically, we derive a strict finite-sample bound showing that any non-trivial confidence level leads to exponential growth in prediction set size for data with inherent uncertainty. The exponent scales linearly with the number of samples and is proportional to the conditional entropy of the data. Additionally, the bound includes a second-order term, dispersion, defined as the variance of the log conditional probability distribution. We show that this bound is achievable in an idealized setting. Finally, we examine a special case of transductive prediction where all test data points share the same label. We show that this scenario reduces to the hypothesis testing problem with empirically observed statistics and provide an asymptotically optimal confidence predictor, along with an analysis of the error exponent.