Transductive Conformal Inference With Adaptive Scores: Proof

Table of Links

• Abstract & Introduction
• Main results
• Application to prediction intervals
• Application to novelty detection
• Conclusion, Acknowledgements and References
• Appendix A: Exact formulas for Pn,m
• Appendix B: Numerical bounds and templates
• Appendix C: Proof
• Appendix D: Explicit control of (16) for α=0
• Appendix E: Proof of Corollary 4.1
• Appendix F: The Simes inequality
• Appendix G: Uniform FDP bound for AdaDetect
• Appendix H: Additional experiments

C Proofs

C.1 Proof of Proposition 2.1

which finishes the proof.

C.2 Proof of Proposition 2.2

If there are no tied scores, which by assumption (NoTies) happens with probability 1, the ranks Ri of the ordered scores are well-defined and the vector (p1, . . . , pm) is only a function of the rank vector (R1, . . . , Rn+m). Namely, Ri ≤ Rj if and only if Si ≤ Sj , and the conformal p-values (1) can be written as

C.3 Proof of Theorem A.1

Proof of (ii) By (Exch),(NoTies) the permutation that orders the scores (S1, . . . , Sn+m) that is σ such that

This event can be formally described as follows:

Proof of (i) By using (27) of (ii), we have

Now, we have

where we have used (ii) and the multinomial coefficient

C.4 Proof of Theorem 2.

First observe that the LHS of (9) is 0 if λ ≥ 1 so that we can assume λ < 1

Let us prove (9) with the more complex bounce

Below, we establish

This leads to