Non-Asymptotic Analysis of Efficiency in Conformalized Regression
This work provides theoretical guidance for data allocation in conformal prediction, addressing efficiency for practitioners in machine learning, though it is incremental as it builds on prior asymptotic analyses.
The paper tackles the problem of quantifying the efficiency of conformal prediction in regression by establishing non-asymptotic bounds on prediction set length deviation, with bounds of order O(1/√n + 1/(α²n) + 1/√m + exp(-α²m)) that capture dependencies on training set size, calibration set size, and miscoverage level.
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 $α$ 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/(α^2 n) + 1/\sqrt{m} + \exp(-α^2 m))$ capture the joint dependence of efficiency on the proper training set size $n$, the calibration set size $m$, and the miscoverage level $α$. The results identify phase transitions in convergence rates across different regimes of $α$, offering guidance for allocating data to control excess prediction set length. Empirical results are consistent with our theoretical findings.