Abstract
In regression problems where there is no known true underlying model, conformal prediction methods enable prediction intervals to be constructed without any assumptions on the distribution of the underlying data, except that the training and test data are assumed to be exchangeable. However, these methods bear a heavy computational cost—and, to be carried out exactly, the regression algorithm would need to be fitted infinitely many times. In practice, the conformal prediction method is run by simply considering only a finite grid of finely spaced values for the response variable. This paper develops discretized conformal prediction algorithms that are guaranteed to cover the target value with the desired probability, and that offer a tradeoff between computational cost and prediction accuracy.
Introduction
In modern machine learning, point predictions are rarely sufficient for high-stakes decision-making. Quantifying uncertainty through prediction intervals is essential. Conformal Prediction (CP) has emerged as the gold standard for this task because it provides "distribution-free" coverage guarantees. Unlike traditional parametric methods, CP ensures that the true value of a target variable $Y$ will fall within a predicted interval with a user-specified probability (e.g., $1-\alpha = 0.90$), requiring only that the data points are exchangeable.
However, a significant bottleneck exists for regression tasks. The standard "full" conformal method requires refitting the underlying model for every possible value the continuous target variable $Y$ could take. Theoretically, this implies an infinite number of model refits. While practitioners often approximate this by using a finite grid of values, this "hack" previously lacked formal theoretical justification. Without a principled framework, a grid that is too coarse risks "undercoverage," where the resulting intervals fail to meet the advertised reliability. This paper formalizes the use of discretization in conformal prediction, providing the necessary theoretical guarantees to bridge the gap between theory and practice.
Methodology: CPDD and CPDM
The authors propose two primary algorithms to address the computational burden of full conformal prediction through discretization:
- Conformal Prediction with Discretized Data (CPDD): This approach involves rounding all training labels ($Y_i$) to a pre-defined finite grid before executing the conformal algorithm. The prediction interval is initially calculated in this "rounded space" and then mapped back to the original continuous space. While straightforward, this method's precision is inherently limited by the resolution of the grid.
- Conformal Prediction with a Discretized Model (CPDM): This more sophisticated method decouples the model fitting from the residual calculation. The model is fitted using discretized labels—significantly reducing the number of required fits—but the residuals (the errors used to determine the interval width) are computed using the original, unrounded labels.
The core theoretical contribution of this work is Theorem 2, which proves that both CPDD and CPDM maintain the desired coverage probability ($1-\alpha$). Crucially, the theorem accounts for data-dependent grids, showing that discretization does not break the exchangeability required for valid conformal inference, provided a small, quantifiable penalty is applied.
Experimental Setup
To validate these methods, the authors conducted experiments using simulated high-dimensional data, where the goal was to compare the proposed discretized methods against an "Oracle" baseline (which assumes perfect knowledge of the data distribution).
- Configuration: The experiments utilized a high-dimensional setting with $p=200$ features and varying sample sizes ($n=100$ and $n=400$).
- Base Learner: Lasso regression was employed as the underlying model.
- Data Generation: Features were drawn from a Gaussian distribution, while the response variable was generated via a non-linear mean function. This setup ensured that the linear Lasso model served as an approximation, reflecting real-world scenarios where the true model is unknown.
Key Insights and Results
The Superiority of CPDM
A major finding is that CPDM is significantly more powerful than the naive CPDD approach. Because CPDM utilizes original values for residual calculations, it can produce prediction intervals that are narrower than the grid spacing itself. This allows practitioners to achieve high-precision intervals without needing an excessively fine (and computationally expensive) grid.
Stability and Sample Size
The research highlights a synergistic relationship between sample size ($n$) and grid density ($M$). As the sample size increases, the model becomes more stable, meaning the "noise" introduced by rounding labels has a diminishing impact on the quality of the prediction interval. In the $n=400$ simulation, CPDM achieved intervals nearly as narrow as the Oracle baseline even with relatively low grid densities.
Theoretical Safety
Both CPDD and CPDM consistently met or exceeded the target 90% coverage rate across all tested grid sizes. This confirms that rounding is theoretically safe and that the common "informal" way of rounding—which often fails to provide promised coverage on coarse grids—can be replaced by these rigorous discretized alternatives.
Limitations and Future Directions
While discretized CP offers a massive speedup over the theoretical "infinite" version, it still requires $M$ model fits. For extremely large models, such as deep neural networks, even $M=20$ fits may be computationally taxing compared to "Split Conformal" methods, which only require a single fit but typically yield wider, less efficient intervals.
Additionally, while the paper proves that data-dependent grids are valid, it does not yet offer an automated mechanism for selecting the optimal grid density for a given dataset. Future work may explore the application of these discretization techniques to other variants of conformal inference and the development of adaptive grid selection strategies.
Summary updated