Summary
This papers proposes a way to reduce the randomness in novelty detection methods (detecting out-of-distribution points) that are based on the split-conformal inference paradigm. This is done by ensembling over several ($K$) train-validation splits of the dataset. The main technical point is to aggregate the evidence from the $K$ individual predictions by averaging their E-values, as a replacement to considering the p-value in the traditional approach with only one train-validation split. It is shown that the FDR (false discovery rate) can still be controlled with these quantities. The method is further enhanced by using certain weighted averages of the E-values, taking into account the estimated powers of each one. The methods are evaluated on synthetic and real data, showing that the proposed derandomized method works better if the fraction of outliers is larger.
Strengths
The proposed novelty detection approach is original in that it combines evidences from different algorithm runs into a single evidence score. This required a formulation of the algorithms' evidences in terms of E-values instead of p-values that are commonplace for conformal methods, to avoid a loss in detection power. While prior novelty detection works have touched upon E-values, the current paper succeeds in controlling the FDR based on these E-value evidences. The methodological details (Sec. 3.1) and mathematical proof (Theorems 3.2 and 3.6) of this FDR control are strongly inspired by existing works, but this technique is new in the area of novelty detection.
As to significance, the method does reduce the variance as promised and keeps its FDR guarantee. It has higher power than competitor methods in some regimes, but quite consistently weaker power in other regimes, particularly for low fraction of outliers. Secondly, while the problem and the solution is built around quite specific requirements, it is plausible that the presented techniques can be applied to the derandomization of other inference methods with statistical guarantees, as the authors say in their Conclusion.
The clarity of the paper is exceptional (but see my comments on Appendix S2 below), the explanations and discussions are to the point.
Weaknesses
As the biggest weakness of the paper I see that, despite the novelty of the approach, the considered problem requirements are relatively specific and the solution therefore narrow, as it concerns the de-randomization of certain novelty detection algorithms that are based on conformal inference and that aim at a mathematical control of the FDR.
Also, the method's performance (power) falls behind other methods in certain application regimes. It would be good to have some rules beforehand to know in which regime to apply which method.
If space permits, I would like to see some real data experiments (see Sec. 4.3) in the main text rather than only in the Supplement.
Questions
* Please mention what K is in Fig. 1.
* line 228: Should this be D^(k)_cal \cup D_test?
* How is AdaDetect different from E-AdaDetect with K=1 (Fig. 3)?
* Please carefully re-write the Proof of Theorem 3.6 in Appendix S2, as I believe there are many typos and several things that could be explained better. In particular:
- Please explain the first equality after line 35.
- It seems that the martingale runs from l'=l down to l'=0, correct?
- It would be good to explain in detail, over which random variables the various expectations E after line 26 run and which random variables are held fixed (conditioned on).
- Right-hand-sides of Eq. (S1) and (S2): Should there be t instead of \hat{t}^{(k)}?
- line 31: The word "outliers" should be "inliers"
- Should the inf be changed to sup, or maybe the inequality sign reversed?
- line 34: inside the curly brackets, the l should be l'?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
Yes, this is discussed in a fair way after line 351.