Abstract: Conformal prediction is a method of producing prediction sets that can be applied on top of a wide range of prediction algorithms. The method has a guaranteed coverage probability under the standard IID assumption regardless of whether the assumptions (often considerably more restrictive) of the underlying algorithm are satisfied. However, for the method to be really useful it is desirable that in the case where the assumptions of the underlying algorithm are satisfied, the conformal predictor loses little in efficiency as compared with the underlying algorithm (whereas being a conformal predictor, it has the stronger guarantee of validity). In this paper we explore the degree to which this additional requirement of efficiency is satisfied in the case of Bayesian ridge regression; we find that asymptotically conformal prediction sets differ little from ridge regression prediction intervals when the standard Bayesian assumptions are satisfied.
Introduction
In modern machine learning, point predictions are often insufficient. Reliable uncertainty quantification, typically in the form of prediction intervals, is essential for high-stakes decision-making. Two primary paradigms exist for generating these intervals: parametric methods, such as Bayesian Ridge Regression (BRR), and distribution-free methods, such as Conformal Prediction (CP).
While BRR provides optimal efficiency (the narrowest intervals) under strict Gaussian assumptions, its validity is compromised if those assumptions are violated. Conversely, Conformalized Ridge Regression (CRR) offers a "safety net," guaranteeing coverage under the much broader assumption of Independent and Identically Distributed (IID) data. A critical question remains: does the robustness of CP come at the cost of significantly wider intervals when the parametric assumptions actually hold? This paper demonstrates that for ridge regression, the efficiency loss is asymptotically negligible.
Methodology
The study compares the performance of Bayesian Ridge Regression (BRR) against Conformalized Ridge Regression (CRR). To analyze the asymptotic behavior of these methods, the authors employ the Bahadur representation theorem. This statistical tool allows for the analysis of how the endpoints of prediction intervals behave as the sample size $n$ approaches infinity.
The theoretical framework relies on four standard assumptions (A1–A4):
- Data objects are IID.
- The second-moment matrix of the objects is non-singular.
- Regression weights are independent of the objects.
- Labels are generated with additive Gaussian noise.
Key Results
The centerpiece of the research is Theorem 2, which establishes that the difference between the endpoints of CRR and BRR intervals converges at a rate of $O(n^{-1/2})$. This implies that as the dataset grows, the "conformalization penalty" effectively vanishes, and the CRR intervals become nearly identical to the optimal BRR intervals.
The authors derive a specific variance formula for the difference between the two methods, showing it is proportional to the noise level ($\sigma$) and inversely proportional to the density of the normal distribution at the chosen significance level $\epsilon$.
As illustrated in the figure above, the standard deviation of the difference remains controlled across most significance levels. However, the efficiency gap widens as $\epsilon$ approaches zero. This is because conformal methods rely on empirical quantiles; in the tails of a distribution, data points are naturally sparser, requiring larger sample sizes for the conformal predictor to "catch up" to the parametric model's efficiency.
Discussion and Limitations
While the results are promising, they are primarily asymptotic. In small-sample regimes, CRR may still produce wider intervals than BRR. Specifically, a conformal predictor requires at least $1/\epsilon$ observations to produce a non-trivial interval at significance level $\epsilon$. Furthermore, while CRR maintains validity without Gaussian noise, the proof of its near-optimal efficiency relies on the noise actually being Gaussian.
Future research may extend this analysis to Kernel Ridge Regression, potentially offering similar efficiency guarantees for non-linear and high-dimensional data structures.
Conclusion
This paper provides a theoretical bridge between the robustness of conformal prediction and the efficiency of parametric methods. It proves that for ridge regression, practitioners do not need to choose between a safety guarantee and optimal interval width—asymptotically, they can achieve both.
Summary updated