  In predictive modeling for high-stake decision-making, predictors must be not
only accurate but also reliable. Conformal prediction (CP) is a promising
approach for obtaining the confidence of prediction results with fewer
theoretical assumptions. To obtain the confidence set by so-called full-CP, we
need to refit the predictor for all possible values of prediction results,
which is only possible for simple predictors. For complex predictors such as
random forests (RFs) or neural networks (NNs), split-CP is often employed where
the data is split into two parts: one part for fitting and another to compute
the confidence set. Unfortunately, because of the reduced sample size, split-CP
is inferior to full-CP both in fitting as well as confidence set computation.
In this paper, we develop a full-CP of sparse high-order interaction model
(SHIM), which is sufficiently flexible as it can take into account high-order
interactions among variables. We resolve the computational challenge for
full-CP of SHIM by introducing a novel approach called homotopy mining. Through
numerical experiments, we demonstrate that SHIM is as accurate as complex
predictors such as RF and NN and enjoys the superior statistical power of
full-CP.
