Non-Asymptotic Analysis of Efficiency in Conformalized Regression

AI summary

Authors: Yunzhen Yao (LINX, EPFL), Lie He (corresponding author; MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics), Michael Gastpar (LINX, EPFL) arXiv: 2510.07093v3 [cs.LG], 05 Mar 2026

Overview

• Research area: Machine learning theory — specifically the efficiency (prediction-set size) of split conformal prediction applied to regression, with quantile regressors trained by stochastic gradient descent (SGD).
• Technical level: Advanced. The paper is a pure theory contribution built on measure-theoretic probability, stochastic approximation, and non-asymptotic statistical learning bounds.
• Scope in one sentence: The paper derives finite-sample upper bounds on how far the conformalized prediction interval length deviates from the oracle conditional-quantile interval, as an explicit joint function of training set size n, calibration set size m, and miscoverage level α.

What This Paper Is About

Conformal prediction wraps a trained regression model in a prediction interval that is guaranteed to cover the true label with probability at least 1 − α, but this guarantee says nothing about how wide that interval is. Wider intervals are less informative, so "efficiency" — typically measured by expected interval length — is the key practical question. Prior efficiency analyses for conformalized regression mostly treated α as a fixed constant or bounded only the effect of the calibration set size m, leaving open how the training set size n and the choice of α jointly affect efficiency in finite samples. This paper closes that gap by proving non-asymptotic bounds for conformalized quantile regression (CQR) and conformalized median regression (CMR) when the underlying quantile regressors are trained with SGD.

Key Contributions

1. Finite-sample efficiency bound for CQR-SGD. For Algorithm 1 (CQR trained by SGD), the paper proves an upper bound of order O(1/√n + 1/(α²n) + 1/√m + exp(−α²m)) on the expected deviation of the prediction set length from the oracle interval length (Theorem 3.2), where n is the proper training set size, m is the calibration set size, and α is the miscoverage level.
2. Finite-sample efficiency bound for CMR-SGD. For homoscedastic tasks, CMR-SGD produces symmetric intervals of constant length across inputs, for which the paper derives a non-asymptotic upper bound of analogous order (Theorem 4.1).
3. First (n, m, α)-explicit efficiency analysis with phase transitions. The authors state this is the first analysis establishing upper bounds on interval-length deviation as a joint function of (n, m, α), revealing phase transitions across different α regimes (Section 3.2.1) and yielding concrete guidance on allocating data between training and calibration.
4. Distribution-level assumptions and an optimizer-agnostic framework. Assumptions are placed directly on the data distribution rather than on intermediate quantities such as the induced nonconformity-score distribution (which depends on the trained model). The theorems are presented for SGD, but the analytical framework is not tied to a specific optimizer: bounds extend to other optimizers by substituting their corresponding estimation-error rates.

Main Findings

• CQR bound and its form. Theorem 3.2 states that if m > 8H / min{α, 1−α} and 0 < α ≤ 1/2, then E[| |C(X)| − |C*(X)| |] ≤ O(n^{−1/2} + (α²n)^{−1} + m^{−1/2} + exp(−α²m)), where C*(X) is the oracle interval [q_{α/2}(Y|X), q_{1−α/2}(Y|X)] and H := f_max / f_min.

• CMR bound. Theorem 4.1 gives the same order O(n^{−1/2} + (α²n)^{−1} + m^{−1/2} + exp(−α²m)) for CMR-SGD under Assumptions 4.1, 3.2, 3.3, and 4.2, with the same condition m > 8H / min{α, 1−α}.

• α cannot be chosen arbitrarily small. The bound converges to zero only when α decays slower than n^{−1/2} and m^{−1/2}, i.e., α = ω(max{n^{−1/2}, m^{−1/2}}). If the expected prediction set length must stay within a fixed tolerance of the oracle length, α is not supposed to be chosen arbitrarily small.

• Phase transition in the n-dependent terms. If α = Ω(n^{−1/4}), the two n-dependent terms are of order O(n^{−1/2}); otherwise they are of order O((α²n)^{−1}).

• Phase transition in the m-dependent terms. If α = Ω(√(log m / m)), the two m-dependent terms are of order O(m^{−1/2}); otherwise they are of order O(exp(−α²m)).

• Recovery of a known rate. If α = Ω(max{n^{−1/4}, √(log m/m)}), the overall bound scales as O(n^{−1/2} + m^{−1/2}), which coincides with the rate in Bars and Humbert (2025) under a finite function class assumption.

• Same-order regime. When n = Θ(m), the upper bound simplifies to O(n^{−1/2} + (α²n)^{−1}); Figure 2 illustrates this across regimes of α = Ω(n^{−1}), consistent with the theorem's condition on m.

• Data allocation guidance. In the regime α = Ω(max{n^{−1/4}, √(log m/m)}), the bound reduces to O(n^{−1/2} + m^{−1/2}), so a natural choice is n and m of the same order. When α = Ω(√(log m/m)) and α = ω(n^{−1/4}), the trade-off is between O(m^{−1/2}) and O(1/(αn²)), and balancing them yields m = Θ(α⁴n⁴).

• Quantile regression error under SGD (Theorem 3.1). With step size η_k = 1/(λ_min f_min k), the mean-squared prediction error is bounded by 4λ_max² f_max d / (λ_min³ f_min² n), and the parameter estimation error E[‖θ_n(γ) − θ*(γ)‖₂²] is bounded by 4λ_max² f_max d / (λ_min⁴ f_min² n).

• Quantile crossing does not persist. The proof of Proposition A.4 shows that quantile crossing (lower quantile estimate exceeding the upper estimate) does not occur with high probability once the training set size n is sufficiently large; because the covariate space is bounded, the ground-truth lower and upper quantile functions cannot cross even if they are not parallel.

• Transfer to other optimizers. If the Theorem 3.1 bound is replaced by φ_n with φ_n → 0 as n → ∞, the Theorem 3.2 bound becomes O(φ_n^{1/2} + α^{−2}φ_n + m^{−1/2} + exp(−α²m)).

• Empirical consistency. The abstract and contributions state that empirical results are consistent with the theoretical findings. The provided paper content is truncated before the experimental section, so specific datasets, sample sizes, and model names are not reported in the available text.

Methodology in Plain English

The authors work in the split conformal prediction setting: data is divided into a proper training set of size n and a calibration set of size m. A model is trained on the first part; nonconformity scores are computed on the second; and a quantile of those scores (specifically the ⌈(1−α)(m+1)⌉-th smallest) sets the interval width.

They analyze two variants. CQR estimates the conditional α/2 and 1−α/2 quantile functions with a linear model of the form t_γ(x; θ) = θᵀx, trained by minimizing the pinball loss via SGD with projection onto a bounded parameter set. The score is the maximum of the two one-sided violations, and calibration extends the estimated quantile band into an adaptive, asymmetric interval. CMR is the special case γ = 1/2, where the score is just the absolute residual from the estimated conditional median, producing symmetric intervals.

To get finite-sample efficiency bounds, the authors first bound the SGD estimation error of the quantile regressor (Theorem 3.1), then decompose the interval-length deviation into four pieces, each bounded separately: (i) the quantile regression errors of the trained model, (ii) the population quantile of the score, (iii) the gap between the population quantile and the finite-sample population quantile, and (iv) the gap between that and the empirical calibration quantile. This decomposition is illustrated as a proof outline in Figure 1, with full proofs deferred to Appendices A and B. Key structural assumptions restrict the covariate space to be bounded (‖x‖₂ ≤ B), the response to a bounded interval, the covariance Σ = E[XXᵀ] to be well-conditioned (λ_min I ⪯ Σ ⪯ λ_max I), and the conditional density f_{Y|X}(y|x) to lie between f_min and f_max. The flatness ratio H = f_max/f_min controls constants in the results. The authors then read off how the bound behaves as α, n, and m vary.

Why This Matters

Impact on research: Efficiency analysis of conformal prediction has largely been asymptotic or conditional on fixed α. This work supplies finite-sample, joint (n, m, α) bounds and shows that α controls a phase transition in the convergence rate — a lever prior analyses treated as a constant. It also shifts assumptions away from model-dependent intermediate quantities (like the nonconformity score distribution) and onto the data distribution itself, and its framework is explicitly portable to optimizers other than SGD.

Real-world applications (safety-critical domains cited by the paper as motivation):

• Health care, where prediction intervals feed into clinical decision support and an overly wide interval is as unhelpful as no interval.
• Finance, where uncertainty-aware forecasts underlie risk and trading decisions.
• Autonomous systems, where downstream planning must reason about the uncertainty of learned predictors.
• Any deployment where a fixed data budget must be split between training a model and calibrating it.

Industry relevance: Practitioners choose a miscoverage level α (often 0.1 or 0.05) and a train/calibration split without theoretical guidance on either. The phase-transition results translate directly into rules of thumb — for example, in the regime α = Ω(max{n^{−1/4}, √(log m/m)}) the split should have n and m of the same order, whereas another regime implies m = Θ(α⁴n⁴) — which is directly actionable for teams allocating data under a coverage target.

Future Directions

• Extending beyond linear models. The analysis assumes a linear function class with a convex, compact parameter space. Whether the bounds carry over to nonparametric or neural quantile regressors is left open.
• Beyond i.i.d. data. The paper explicitly notes that its analysis focuses on the i.i.d. setting and that robustness under distribution shift has been studied separately (e.g., Joshi et al., 2025); combining non-asymptotic efficiency bounds with shift robustness is an open direction.
• Optimizer-specific rates. Remark 3.3 shows how to plug in other optimizers' estimation-error rates φ_n, and Remark 3.2 notes that comparable rates can be obtained for non-strongly-convex objectives under the assumptions of Bach and Moulines (2013), where Assumption 3.2 can be weakened to invertibility of E[XXᵀ]. Working out concrete bounds for specific optimizers remains to be done.
• Classification and other prediction-set geometries. The paper addresses regression interval length; efficiency for classification (cardinality of the predicted label set) and extending to the adaptive prediction sets the authors say the bounds apply to are natural follow-ups.

Target Audience

The primary audience is machine learning theorists working on conformal prediction, uncertainty quantification, quantile regression, and stochastic approximation. Secondary audiences include statisticians studying non-asymptotic estimation, and applied researchers or engineers in safety-critical domains who need to justify how they set the miscoverage level and split their data between training and calibration. Readers should be comfortable with empirical process arguments, non-asymptotic error bounds, and the mechanics of split conformal prediction.

Authors’ 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 $α$ 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.