Abstract
In regression, conformal prediction is a general methodology to construct prediction intervals in a distribution-free manner. Although conformal prediction guarantees strong statistical property for predictive inference, its inherent computational challenge has attracted the attention of researchers in the community. In this paper, we propose a new framework, called Trimmed Conformal Prediction (TCP), based on a two-stage procedure: a trimming step and a prediction step. The idea is to use a preliminary trimming step to substantially reduce the range of possible values for the prediction interval, making the subsequent application of conformal prediction far more efficient. TCP can be applied to any regression method and offers both statistical accuracy and computational gains. We demonstrate its implementation in sparse regression settings, with experiments on synthetic and real data validating its empirical performance.
Introduction
In machine learning, point predictions are often insufficient; reliable uncertainty quantification through prediction intervals is essential. Conformal prediction is the gold-standard framework for this, providing "distribution-free" guarantees that hold as long as data points are exchangeable.
However, full conformal prediction is computationally intensive for regression. It requires refitting a model for every possible outcome value $y$ to determine the interval boundaries. For high-dimensional models like the Lasso, this involves thousands of expensive optimizations. While "split conformal prediction" is faster, it typically produces much wider, less useful intervals because it only uses a fraction of the data for training.
Methodology
Trimmed Conformal Prediction (TCP) addresses these challenges by splitting the task into two distinct steps:
- Trimming Step: A "fast but loose" method constructs a wide initial interval ($\mathcal{Y}_{trim}$), quickly discarding outcome values that are highly unlikely. The authors propose techniques like RidgeTrim, which uses the closed-form solution of Ridge regression for near-instantaneous residual calculation, and SplitTrim, which uses a small data split for a rough estimate.
- Prediction Step: The more accurate but slower conformal prediction algorithm (e.g., full Lasso) is applied only within the restricted range identified in the trimming step.
Mathematically, the errors from both steps are additive. If trimming uses a significance level $\alpha_{trim}$ and prediction uses $\alpha_{predict}$, the final interval is guaranteed to cover the true value with at least $1 - \alpha_{trim} - \alpha_{predict}$ probability.
Key Results
Statistical Precision
TCP bridges the gap between the speed of split conformal methods and the accuracy of full conformal methods. In simulations, TCP variants produced prediction intervals significantly narrower than standard split conformal methods. As shown in Figure 1, while standard Split methods show increasing interval widths as dimensionality $p$ grows, TCP methods maintain much tighter bounds.
Computational Efficiency
The primary computational benefit of TCP is the reduction of the "Trial set width"—the range of $y$ values the model must evaluate. As illustrated in Figure 2, methods like SplitTrim and RidgeTrim drastically reduce this search space compared to naive approaches, often by 60-90%.
Real-World Performance
On real-world data from the Capital Bikeshare program, TCP maintained the target 90% coverage rate while providing tighter intervals than competitors. However, testing on temporal data (the "last day") saw coverage drop to ~86%, highlighting that while TCP is distribution-free, it still relies on the fundamental assumption of data exchangeability.
Conclusion
Trimmed Conformal Prediction provides a scalable framework for high-dimensional predictive inference. By intelligently pruning the search space, TCP allows the use of sophisticated, computationally expensive models for conformal prediction that were previously impractical. Future work may extend this framework to non-linear models and explore adaptive trimming strategies to further optimize the trade-off between speed and precision.
Summary updated