Derandomized Novelty Detection with FDR Control via Conformal E-values

1.1 Background and motivation

• Novelty detection tests whether new samples match a reference distribution; the paper uses model-free machine-learning scores and conformal inference, but split-conformal results vary with the random data split.Split-conformal calibration yields p-values for testing outliers and supports FDR control with the Benjamini-Hochberg filter under mild exchangeability assumptions.Source: §1.1 · pp. 1–2

1.2 Main contributions

• The proposed martingale-based method aggregates conformal e-values across dependent tests, then adaptively weights them using estimated out-of-sample model accuracy to boost power.The paper reports that this approach can achieve power comparable to standard conformal inference while mitigating algorithmic randomness.Source: §1.2 · pp. 2–3

1.3 Related work

• Generic p-to-e calibrators can have low power with discrete conformal p-values, motivating a novel e-value construction inspired by Ren and Barber (2023).Unlike Ignatiadis et al. (2023), the method constructs e-values simultaneously for the test set to control FDR; simulations report higher power, especially with many outliers.Source: §1.3 · p. 3
• Data-driven weighting re-purposes transductive conformal inference to use information in the test data when calibrating e-values, boosting outlier-detection power.This direction is similar to Marandon et al. (2022) and Liang et al. (2022). Full-conformal inference and cross-validation+ can yield more stable p-values, but their dependencies complicate FDR control without power loss or expensive computation.Source: §1.3 · p. 3

2.1 Notation and problem setup

• The task tests whether each unlabeled test point is an inlier from the exchangeable data distribution, aiming to discover true outliers while controlling FDR.The observed training data and test points are assumed exchangeable, or independently and identically distributed.Source: §2.1 · p. 3

2.2 Review of FDR control with conformal p-values

• Split-conformal p-values use calibration-set score ranks; under the null they are valid, discrete uniform values, but share calibration data and are dependent.Larger scores indicate stronger outlier evidence, and ties may be broken randomly.Source: §2.2 · p. 4
• The BH filter applies an adaptive score threshold to dependent conformal p-values and controls FDR at level α.Its threshold estimates false discoveries from calibration scores relative to the total discoveries; Bates et al. (2023) proved FDR control below α.Source: §2.2 · p. 4

2.3 Review of FDR control with AdaDetect

• AdaDetect uses a permutation-invariant binary classifier to distinguish training inliers from calibration and test mixtures, but its single calibration subset leaves results randomized.It can use test data to tune hyperparameters toward more discoveries; integrative conformal p-values by Liang et al. (2022) similarly use test data but require labeled outliers.Source: §2.3 · p. 4

3.1 Derandomizing split-conformal inferences

• Each repetition yields conformal e-values that are averaged across splits with normalized weights, and larger values indicate stronger evidence that a test point is an outlier.The construction has a relaxed average-validity property rather than requiring each e-value to have expected value at most one; the paper reports that it typically has higher power than standard p-to-e calibrators.Source: §3.1 · p. 5
• Under conditional exchangeability of inliers and null test points, the eBH filter applied to the aggregated e-values controls FDR at the target level α.The guarantee holds regardless of the internal BH hyper-parameter αbh and does not require inliers to be independent of outliers.Source: §3.1 · p. 6

3.2 Leveraging data-driven weights

• Data-driven weights preserve FDR validity when each weight is invariant to permutations of a test point and its corresponding calibration samples.One example weights each split by a t-statistic comparing the largest ⌈ntest · γ⌉ calibration-test scores with the remaining scores, using prior information that the test outlier proportion is approximately γ.Source: §3.2 · p. 6

3.3 Derandomizing AdaDetect with E-AdaDetect

• E-AdaDetect extends the method to K models trained using the unordered union of calibration and test data in each split.The permutation-invariant weighting condition allows this extension while retaining the validity result for adaptive weights.Source: §3.3 · p. 6

3.4 Tuning the FDR hyper-parameter

• The paper sets αbh = α/10 as a choice that generally works well, while noting that higher power can sometimes result from other values, especially with many test outliers.Changing αbh has competing effects on the number of test and calibration scores above the rejection threshold; averaging e-values across choices would preserve validity by linearity of expectation.Source: §3.4 · pp. 6–7

4.1 Setup and performance metrics

• Across 100 analyses of the same fixed data and test set, the study evaluates average power, false discovery proportion, and variability in rejections at target FDR level α = 0.1.The average false discovery proportion is distinct from FDR, although the authors report that it is controlled in practice across the considered datasets.Source: §4.1 · p. 7

4.2 Experiments with synthetic data

• Synthetic experiments use 100-dimensional Gaussian data with 10% test-set outliers by default, and compare both methods using the same logistic-regression classifier.The reference set has 2,000 inliers split evenly between training and calibration, and the test set has 1,000 points.Source: §4.2 · p. 7, §4.1 · p. 7

4.2.1 The effect of the signal strength

• With strong signals, E-AdaDetect reduces variability and can exceed AdaDetect in power, while AdaDetect tends to have higher power when signals are weak.The authors explain that derandomization can retain stable true discoveries while filtering more aleatory false discoveries when signals are strong.Source: §4.2.1 · p. 8, Figure 2 · p. 8

4.2.2 The effect of the number of analyses K

• At signal amplitude 3.4, increasing K reduces E-AdaDetect's variability and tends to lower false discoveries; power appears to rise with K, but may fall for weak signals.The authors recommend larger K when higher power is expected; K = 1 does not derandomize and has lower power than AdaDetect, partly because eBH is conservative.Source: §4.2.2 · p. 8, Figure 3 · p. 9

4.2.3 The effect of the weighting strategy

• On synthetic data, t-test weighting is the most effective scheme and often yields much higher power than uniform or average-score weighting.The experiment varies logistic-regression regularization across K = 10 analyses to induce greater variability in predictive rules.Source: §4.2.3 · pp. 8–9, Figure 4 · p. 9
• On four real datasets, both data-driven weighting schemes yield more discoveries than uniform weighting, with t-test most powerful and lower variability.The figure caption reports that t-test weighting also controls FDR below the nominal 10% level.Source: §4.2.3 · p. 9, Figure 5 · p. 10

4.3 Additional results from experiments with synthetic and real data

• Supplementary experiments find lower power for pointwise p-to-e calibrators than for the martingale method, and favorable comparisons with an alternative e-value method in specified settings.The comparison is especially favorable when the test set contains numerous outliers or the nominal FDR level is not too low; further real-data experiments report relatively high power while mitigating randomness.Source: §4.3 · pp. 9–10

5 Discussion

• E-values can aggregate dependent tests and support efficient FDR control under arbitrary dependence, making them useful for conformal derandomization despite often weaker evidence for a single hypothesis.Their individual evidence can accumulate across many hypotheses; this combination had been used to derandomize knockoffs but not fully exploited for conformal inference.Source: §5 · p. 10
• The approach could extend to conformal regression intervals, classification prediction sets with false coverage rate control, and cross-validation+ (Lei and Wasserman, 2014; Romano et al., 2019; Lei et al., 2013; Romano et al., 2020; Weinstein and Ramdas, 2020; Barber et al., 2021).These are proposed directions for future work beyond split-conformal and AdaDetect novelty-detection inferences.Source: §5 · p. 10
• The method is more computationally expensive and may yield fewer findings than randomized alternatives, especially when few discoveries are expected, so practitioners should weigh stability gains against possible power loss.For very large data sets, the added cost may limit the number K of analysis repetitions.Source: §5 · p. 10
• Proofs, additional supporting results, and software for implementing the algorithms and reproducing the numerical experiments are provided in the Supplementary Material and project repository.The repository is https://github.com/Meshiba/derandomized-novelty-detection.Source: §5 · p. 10

Abstract

• The supplementary document provides mathematical proofs supporting the paper.Source: Abstract · p. 14
• It also supplies additional details about the paper.Source: Abstract · p. 14
• The document includes comparisons to baseline methods.Source: Abstract · p. 14
• It contains other supporting information accompanying the paper.Source: Abstract · p. 14

Algorithm S1

• With fixed model weights, the algorithm computes conformal e-values over K data splits, forms a weighted average for each test point, and passes these values to the eBH filter.Each split uses calibration and test scores and a threshold depending on αbh.Source: S1 Algorithmic details · p. 15

Algorithm S2

• The eBH filter sorts aggregated e-values and rejects hypotheses whose e-values meet the threshold N/(α·i) at the largest qualifying rank.It returns the set of hypotheses whose e-values are at least the e-value at that rank.Source: S1 Algorithmic details · p. 15

Algorithms S3–S4

• Data-adaptive aggregation computes unnormalized model weights, normalizes them to sum to one, and averages the split-specific e-values before eBH filtering.The same aggregation is used in the variant that adds AdaDetect training, where the calibration and test data are treated as outliers for training.Source: S1 Algorithmic details · pp. 15–16

Algorithm S5

• The t-test weighting procedure sorts scores, divides them into groups using a guessed outlier proportion, and outputs the absolute test statistic as the model weight.The groups have sizes N − ⌈γN⌉ and ⌈γN⌉.Source: S1 Algorithmic details · p. 16

Algorithm S6

• The trimmed-mean weighting procedure averages the lowest N − ⌈γN⌉ sorted scores and sets the model weight to the exponential of the negative mean.The input includes a guess γ for the proportion of outliers.Source: S1 Algorithmic details · p. 16

S2 Mathematical proofs

• The proof of Theorem 3.2 follows from Theorem 3.6.The passage directs readers to the proof of Theorem 3.6.Source: S2 Mathematical proofs · p. 17
• Theorem 3.6 uses a martingale argument similar to Rava et al. (2021), with optional stopping applied to a martingale conditional on ˜D(k).The proof identifies M(k)(t) as a conditional martingale and invokes the optional stopping theorem.Source: S2 Mathematical proofs · pp. 17–18
• The proof defines thresholds by the number of inliers whose scores exceed them and assumes no ties, which can be ensured by adding negligible noise.Between consecutive thresholds, the differing score belongs either to a calibration point or a null test point; the proof considers these as mutually exclusive events.Source: S2 Mathematical proofs · pp. 17–18

• Synthetic experiments use logistic regression with scikit-learn’s default ridge regularization for binary classification and an RBF one-class kernel SVM with the default kernel width.The models are used to compute scores.Source: S3 Implementation details for… · p. 19
• Real-data binary classification uses a random forest with 100 estimators and maximum depth 10, with other hyperparameters at scikit-learn defaults.Source: S3 Implementation details for… · p. 19
• Real-data one-class classification uses an isolation forest with 100 estimators, each fitted to a random subset of min(256, n_samples) training samples; other hyperparameters use scikit-learn defaults.Source: S3 Implementation details for… · p. 19
• Unless otherwise specified, derandomization sets αbh = 0.1 · α, where α is the target FDR level; experiments ran on a local CPU cluster.Source: S3 Implementation details for… · p. 19

S4.1 Derandomized AdaDetect

• Across 100 realizations, FDR was controlled; at high K in the low-power regime, E-AdaDetect reduced selection variance at the cost of power.Inconsistent selections by the base methods in the low-power regime are likely filtered out by derandomization; average FDR and power were also evaluated across 100 realizations as K varied.Source: S4.1 Derandomized AdaDetect · p. 19, Figure S1 · p. 20, Figure S2 · p. 20

S4.2 Derandomized One-Class Conformal

• For OC-Conformal, both methods controlled false discovery proportion, while E-OC-Conformal had lower false discovery proportion and variability, often at the cost of power.Average FDR and power across 100 realizations confirmed the method’s validity.Source: S4.2 Derandomized One-Class Conformal · p. 19, Figure S4 · p. 21, Figure S5 · p. 21

S4.3 Hyper-parameter tuning

• For E-OC-Conformal, αbh=α/2 suited large outlier proportions and αbh=α/10 suited small proportions; E-AdaDetect was robust with αbh=α/10 across studied scenarios.The remaining supplementary experiments use αbh=α/2 for E-OC-Conformal and αbh=α/10 for E-AdaDetect.Source: S4.3 Hyper-parameter tuning · p. 22, Figure S7 · p. 23

S5.1 Review of p-to-e calibrators

• P-to-e calibrators transform valid conformal p-values into e-values; the VS calibrator is an informative but invalid optimistic baseline, while integrating over ϵ avoids choosing that hyperparameter.Source: S5.1 Review of p-to-e calibrators · p. 24

S5.1.1 Comparing p-to-e to the martingale-based approach

• P-to-e calibrators have lower power than the martingale-based method with OC-Conformal; even the relatively stronger VS calibrator is considerably less powerful and produces invalid e-values.In the synthetic experiments, p-to-e power was nearly zero; larger calibration sets can help because they permit smaller minimum conformal p-values and thus larger calibrator outputs. The authors omit AdaDetect comparisons because the approach requires a large calibration set that can lower AdaDetect’s power.Source: S5.1.1 Comparing p-to-e to the… · p. 25, Figure S8 · p. 26

S5.2 Review of soft-rank permutation e-test

• Soft-rank e-values use each test point’s relative rank against calibration scores, then apply a nonnegative, order-preserving transformation to construct valid e-values.The reported experiments use r = 500 for AdaDetect and r = 75 for OC-Conformal, selected to account for power trade-offs.Source: S5.2 Review of soft-rank permutation… · pp. 26–27

S5.2.1 Comparing soft-rank e-values to the martingale-based e-values

• The martingale-based method is more powerful than soft-rank, with the gap increasing as test-outlier proportion rises, and it adapts better to target FDR levels.The comparison varies outlier proportion while holding randomized-benchmark power near 80%; the martingale method’s α_bh is proportional to target FDR, whereas soft-rank’s r is fixed.Source: S5.2.1 Comparing soft-rank e-values to… · p. 29, Figure S11 · p. 29

S6.1 Derandomized AdaDetect

• AdaDetect comparisons used K = 10 splits and 100 repeated analyses of the same data, with 3,000 reference inliers and a 1,000-sample test set.The test-set outlier proportion was controlled; the reference set was split into training and calibration subsets of 2,000 and 1,000, respectively.Source: S6.1 Derandomized AdaDetect · p. 29

S6.2 Derandomized One-Class Conformal

• For OC-Conformal, the study increased the number of analyses to K = 70 because it was less powerful and less stable than AdaDetect on these data sets.For KDDCup99 with 40% outliers, soft-rank had the highest selection variance among the studied methods; increasing K was suggested as one way to reduce it.Source: S6.2 Derandomized One-Class Conformal · p. 32

S6.1 Derandomized AdaDetect

• With 10% outliers, AdaDetect variants controlled average false discoveries below α = 0.1 with similar power, while derandomized findings were more stable; at 40%, martingale-based derandomization outpowered soft-rank.The comparisons used four data sets: musk, shuttle, KDDCup99, and credit card.Source: S6.1 Derandomized AdaDetect · p. 29, Figure S16 · p. 32

S6.2 Derandomized One-Class Conformal

• For OC-Conformal, derandomization reduced variability and controlled false discoveries but traded off power against the randomized method; martingale-based power was higher at larger outlier proportions.At 10% outliers, soft-rank had comparable and possibly slightly higher power; results were reproducible across 100 random subsamples, with FDR controlled.Source: S6.2 Derandomized One-Class Conformal · p. 32, Figure S17 · p. 33, Figure S19 · p. 35