[2510.07093] Non-Asymptotic Analysis of Efficiency in Conformalized Regression

Computer Science > Machine Learning arXiv:2510.07093 (cs) [Submitted on 8 Oct 2025 (v1), last revised 5 Mar 2026 (this version, v3)] Title:Non-Asymptotic Analysis of Efficiency in Conformalized Regression Authors:Yunzhen Yao, Lie He, Michael Gastpar View a PDF of the paper titled Non-Asymptotic Analysis of Efficiency in Conformalized Regression, by Yunzhen Yao and 2 other authors View PDF Abstract:Conformal prediction provides prediction sets with coverage guarantees. The informativeness of conformal prediction depends on its efficiency, typically quantified by the expected size of the prediction set. Prior work on the efficiency of conformalized regression commonly treats the miscoverage level $\alpha$ as a fixed constant. In this work, we establish non-asymptotic bounds on the deviation of the prediction set length from the oracle interval length for conformalized quantile and median regression trained via SGD, under mild assumptions on the data distribution. Our bounds of order $\mathcal{O}(1/\sqrt{n} + 1/(\alpha^2 n) + 1/\sqrt{m} + \exp(-\alpha^2 m))$ capture the joint dependence of efficiency on the proper training set size $n$, the calibration set size $m$, and the miscoverage level $\alpha$. The results identify phase transitions in convergence rates across different regimes of $\alpha$, offering guidance for allocating data to control excess prediction set length. Empirical results are consistent with our theoretical findings. Comments: Subjects: Machine Learning (...