# Non-Asymptotic Analysis of Efficiency in Conformalized Regression

arXiv: https://arxiv.org/abs/2510.07093 · HTML: https://mlsanity.com/paper/2510.07093/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 73 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Builds on (most cited first, 30 of 32)

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Safe Planning in Dynamic Environments using Conformal Prediction](https://mlsanity.com/paper/2210.10254/) (2022)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Distributional conformal prediction](https://mlsanity.com/paper/1909.07889/) (2019)
- [A comparison of some conformal quantile regression methods](https://mlsanity.com/paper/1909.05433/) (2019)
- [CD-split and HPD-split: efficient conformal regions in high dimensions](https://mlsanity.com/paper/2007.12778/) (2020)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees](https://mlsanity.com/paper/2405.10301/) (2024)
- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Criteria of efficiency for conformal prediction](https://mlsanity.com/paper/1603.04416/) (2016)
- [Minimum Volume Conformal Sets for Multivariate Regression](https://mlsanity.com/paper/2503.19068/) (2025)
- [Smoothed Quantile Regression with Large-Scale Inference](https://mlsanity.com/paper/2012.05187/) (2020)
- [An Information Theoretic Perspective on Conformal Prediction](https://mlsanity.com/paper/2405.02140/) (2024)
- [Backward Conformal Prediction](https://mlsanity.com/paper/2505.13732/) (2025)
- [On the Expected Size of Conformal Prediction Sets](https://mlsanity.com/paper/2306.07254/) (2023)
- [Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization](https://mlsanity.com/paper/2502.13030/) (2025)
- [Volume Optimality in Conformal Prediction with Structured Prediction Sets](https://mlsanity.com/paper/2502.16658/) (2025)
- [Generalization and Informativeness of Conformal Prediction](https://mlsanity.com/paper/2401.11810/) (2024)
- [On Volume Minimization in Conformal Regression](https://mlsanity.com/paper/2502.09985/) (2025)
- [Scale-free Networks Well Done](https://mlsanity.com/paper/1811.02071/) (2018)
- [Online Quantile Regression](https://mlsanity.com/paper/2402.04602/) (2024)
- [PAC-Bayes Generalization Certificates for Learned Inductive Conformal Prediction](https://mlsanity.com/paper/2312.04658/) (2023)
- [Improving the statistical efficiency of cross-conformal prediction](https://mlsanity.com/paper/2503.01495/) (2025)
- [Online Conformal Prediction with Efficiency Guarantees](https://mlsanity.com/paper/2507.02496/) (2025)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)

## Built on by (most cited first, 2 of 2)

- [View-Structured Conformal Prediction for 3D Gaussian Splatting](https://mlsanity.com/paper/2609.10307/) (2026)
- [Valid and Efficient Split Conformal Regression for Time Series](https://mlsanity.com/paper/2609.33866/) (2026)

## Abstract (arXiv)

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 O(1/√n + 1/(α2 n) + 1/√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.