Universality of conformal prediction under the assumption of randomness

Vladimir Vovk
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-18, 2026.

Abstract

Conformal predictors provide set or functional predictions that are valid under the assumption of randomness, i.e., under the assumption of independent and identically distributed data. The question asked in this paper is whether there are predictors that are valid in the same sense under the assumption of randomness and that are more efficient than conformal predictors. The answer is that the class of conformal predictors is universal in that only limited gains in predictive efficiency are possible. The previous work in this area has relied on the algorithmic theory of randomness and so involved unspecified constants, whereas this paper’s results are much more practical. They are also shown to be optimal in some respects.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-vovk26a, title = {Universality of conformal prediction under the assumption of randomness}, author = {Vovk, Vladimir}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--18}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/vovk26a/vovk26a.pdf}, url = {https://proceedings.mlr.press/v313/vovk26a.html}, abstract = {Conformal predictors provide set or functional predictions that are valid under the assumption of randomness, i.e., under the assumption of independent and identically distributed data. The question asked in this paper is whether there are predictors that are valid in the same sense under the assumption of randomness and that are more efficient than conformal predictors. The answer is that the class of conformal predictors is universal in that only limited gains in predictive efficiency are possible. The previous work in this area has relied on the algorithmic theory of randomness and so involved unspecified constants, whereas this paper’s results are much more practical. They are also shown to be optimal in some respects.} }
Endnote
%0 Conference Paper %T Universality of conformal prediction under the assumption of randomness %A Vladimir Vovk %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-vovk26a %I PMLR %P 1--18 %U https://proceedings.mlr.press/v313/vovk26a.html %V 313 %X Conformal predictors provide set or functional predictions that are valid under the assumption of randomness, i.e., under the assumption of independent and identically distributed data. The question asked in this paper is whether there are predictors that are valid in the same sense under the assumption of randomness and that are more efficient than conformal predictors. The answer is that the class of conformal predictors is universal in that only limited gains in predictive efficiency are possible. The previous work in this area has relied on the algorithmic theory of randomness and so involved unspecified constants, whereas this paper’s results are much more practical. They are also shown to be optimal in some respects.
APA
Vovk, V.. (2026). Universality of conformal prediction under the assumption of randomness. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-18 Available from https://proceedings.mlr.press/v313/vovk26a.html.

Related Material