This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Ulysse Gazin, Universit´e Paris Cit´e and Sorbonne Universit´e, CNRS, Laboratoire de Probabilit´es, Statistique et Mod´elisation,
(2) Gilles Blanchard, Universit´e Paris Saclay, Institut Math´ematique d’Orsay,
(3) Etienne Roquain, Sorbonne Universit´e and Universit´e Paris Cit´e, CNRS, Laboratoire de Probabilit´es, Statistique et Mod´elisation.
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