We begin by proving the lower bound on coverage. The formal proof of this statement is standard at this point, so we simply refer to [3] for the remaining technical details. The proof for the upper bound also immediatelyfollowsfrom(S6)byapplyingLemma2in[3]. The proof is essentially an application of the main result in [2]. This will become apparent after we reduce our claim to the setting in the aforementioned paper.

Here, we consider the jackknife+--i.e., Algorithm S1 describes the extension of Algorithm 1 discussed in Section 2.5, which ensures The validity of this algorithm is established by the following result. We begin by proving the lower bound on coverage. This will become apparent after we reduce our claim to the setting in the aforementioned paper. This is easy to verify. Let σ (1),...,σ ( n + m) be the permutation of the data points corresponding to Σ, so that (ΣA Σ S3.1 Implementation details We have applied the following black-box classification methods to estimate label probabilities: JK+ is omitted for computational reasons. The performances of the different methods on data generated from this model are compared in Figure S3.

Conformal inference, cross-validation+, and the jackknife+ are hold-out methods that can be combined with virtually any machine learning algorithm to construct prediction sets with guaranteed marginal coverage. In this paper, we develop specialized versions of these techniques for categorical and unordered response labels that, in addition to providing marginal coverage, are also fully adaptive to complex data distributions, in the sense that they perform favorably in terms of approximate conditional coverage compared to alternative methods. The heart of our contribution is a novel conformity score, which we explicitly demonstrate to be powerful and intuitive for classification problems, but whose underlying principle is potentially far more general. Experiments on synthetic and real data demonstrate the practical value of our theoretical guarantees, as well as the statistical advantages of the proposed methods over the existing alternatives.