Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.04631 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914618461388800 |
|---|---|
| author | Behboodi, Arash Correia, Alvaro H. C. Massoli, Fabio Valerio Louizos, Christos |
| author_facet | Behboodi, Arash Correia, Alvaro H. C. Massoli, Fabio Valerio Louizos, Christos |
| contents | 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 the transductive methods based on the approximate conditional distribution can approach this bound. Inspired by this setup, we introduce a practical transductive prediction algorithm that surpasses Bonferroni methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04631 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fundamental bounds on efficiency-confidence trade-off for transductive conformal prediction Behboodi, Arash Correia, Alvaro H. C. Massoli, Fabio Valerio Louizos, Christos Machine Learning Information Theory 94A15, 62G10, 68T01 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 the transductive methods based on the approximate conditional distribution can approach this bound. Inspired by this setup, we introduce a practical transductive prediction algorithm that surpasses Bonferroni methods. |
| title | Fundamental bounds on efficiency-confidence trade-off for transductive conformal prediction |
| topic | Machine Learning Information Theory 94A15, 62G10, 68T01 |
| url | https://arxiv.org/abs/2509.04631 |