Approximating Full Conformal Prediction at Scale via Influence Functions
  Conformal prediction (CP) is a wrapper around traditional machine learning
models, giving coverage guarantees under the sole assumption of
exchangeability; in classification problems, for a chosen significance level
$\varepsilon$, CP guarantees that the number of errors is at most
$\varepsilon$, irrespective of whether the underlying model is misspecified.
However, the prohibitive computational costs of full CP led researchers to
design scalable alternatives, which alas do not attain the same guarantees or
statistical power of full CP. In this paper, we use influence functions to
efficiently approximate full CP. We prove that our method is a consistent
approximation of full CP, and empirically show that the approximation error
becomes smaller as the training set increases; e.g., for $10^{3}$ training
points the two methods output p-values that are $<10^{-3}$ apart: a negligible
error for any practical application. Our methods enable scaling full CP to
large real-world datasets. We compare our full CP approximation ACP to
mainstream CP alternatives, and observe that our method is computationally
competitive whilst enjoying the statistical predictive power of full CP.
