Fast full conformal prediction for multiple test points

Conformal prediction has emerged as a useful tool for providing valid predictive inference regardless of the data distribution. However, its implementation can be computationally intensive, even for small-scale data sets. Hence, it is typically prohibitive to construct full conformal prediction intervals for multiple test points, which limits its practicality. As an alternative, a sample-split approach can be used, but it usually provides wider prediction intervals, as it does not use all observations in the data for training. This paper attempts to fill this gap by developing a scalable conformal prediction algorithm for multiple test points. We find that when we use kernel ridge regression for the underlying prediction method, it is possible to reuse some computation in constructing prediction intervals across multiple test points, which enables us to avoid repeating the heavy computation of a matrix inverse for each test point. We propose an efficient algorithm that employs this fact, dramatically reducing the computational cost. We demonstrate the effectiveness and practical usefulness of the proposed algorithm in numerical experiments.