Technical Summary: Collective Outlier Detection and Enumeration with Conformalized Closed Testing

1. Problem Statement

The paper addresses the challenge of collective outlier detection and enumeration in scenarios where individual outliers are difficult to identify due to sparsity, weak signals, or elusiveness. While traditional conformal inference has focused on individual-level outlier identification (controlling the False Discovery Rate for specific data points), this approach often lacks power when outliers do not exhibit significant deviations in isolation.

The authors define two primary tasks for a test set $Z_{m+1}, \dots, Z_{m+n}$ against a reference set of inliers $Z_1, \dots, Z_m$:

1. Outlier Detection: Testing the global null hypothesis that a subset of the test data contains no outliers.
2. Outlier Enumeration: Estimating the number of outliers within a subset by providing a simultaneous lower confidence bound, without necessarily pinpointing the exact identity of each outlier.

The core difficulty lies in the fact that standard individual-level tests (e.g., Benjamini-Hochberg applied to conformal p-values) may fail to reject the global null or provide informative bounds when signals are weak or sparse. Furthermore, selecting the optimal machine learning classifier and statistical test procedure a priori is difficult, and "cherry-picking" based on data leads to selection bias and invalid inference.

2. Methodology: ACODE

The authors propose ACODE (Automatic Conformal Outlier Detection and Enumeration), a flexible, distribution-free framework that integrates conformal inference, closed testing, and adaptive rank tests.

2.1 Conformal Scoring and Splitting

The method begins by generating conformity scores using machine learning classifiers trained to distinguish outliers from inliers.

• Classifiers: The framework supports both one-class classifiers (trained only on inliers) and binary classifiers (trained via positive-unlabeled learning).
• Score Generation: A function $\hat{s}$ maps data points to scalar scores. To ensure validity, the method employs sample splitting. A tuning set is used to select the best classifier and testing procedure, while a separate calibration set is used to generate conformal p-values for the test set. This separation preserves the exchangeability of inlier scores conditional on the selected procedure, preventing selection bias.

2.2 Local Testing Procedures

ACODE aggregates conformity scores to test local hypotheses $H_S$ (that a subset $S$ contains no outliers). The paper evaluates a "toolbox" of local tests, each suited for different signal structures:

• Simes Test: Effective for rare, strong signals.
• Fisher's Combination: Effective for dense, weak signals.
• Wilcoxon-Mann-Whitney (WMW): A rank test shown to be the Locally Most Powerful Rank (LMPR) test under specific Lehmann alternatives (where outliers follow the distribution of the maximum of two inliers).
• Shiraishi's LMPR Test: A generalization of WMW for arbitrary outlier distributions.
• Adaptive Rank Test: A data-driven extension of Shiraishi's test that estimates the unknown outlier density $g$ non-parametrically. Theoretical results (Theorem 2) show this adaptive test achieves the same local asymptotic power as an oracle test with known $g$.

2.3 Closed Testing for Enumeration

To move from local tests to global enumeration, ACODE employs the closed testing principle (Marcus et al., 1976).

• Mechanism: The method tests all possible intersection hypotheses $H_J$ for subsets $J \subseteq [n]$. A lower confidence bound $d(S)$ for the number of outliers in any subset $S$ is derived by finding the largest subset $K \subseteq S$ for which the null hypothesis cannot be rejected after multiplicity adjustment.
• Validity: Proposition 1 guarantees that if the local tests are valid, the resulting lower bounds satisfy simultaneous coverage: $P(d(S) \le |I_1 \cap S| \text{ for all } S) \ge 1-\alpha$.
• Computational Efficiency: While closed testing is generally exponential, the paper utilizes polynomial-time shortcuts (Goeman et al., 2019; Tian et al., 2023) for Simes, WMW, and Fisher tests, making the method scalable to large datasets.

2.4 Data-Driven Adaptivity

A key innovation is Algorithm 3, which automates the selection of the classifier and local test.

• Process: The algorithm evaluates multiple combinations of classifiers and tests on a tuning set to maximize the lower bound (for enumeration) or minimize the p-value (for detection).
• Bias Control: By using a separate tuning set and then re-evaluating the selected combination on the full calibration/test split, the method avoids the inflated Type-I error rates associated with naive "cherry-picking."

3. Key Contributions

The paper makes three primary methodological contributions:

1. ACODE Framework: Introduces a principled, data-driven method for outlier enumeration that automatically selects the optimal machine learning classifier and two-sample testing procedure. It integrates closed testing with conformal inference to provide rigorous, simultaneous lower bounds on the number of outliers.
2. Theoretical Extensions: Provides asymptotic approximations for the null distributions of Shiraishi's locally most powerful rank test and its adaptive version under exchangeable (rather than strictly i.i.d.) conformity scores. This extension is crucial for validity in the split-conformal setting.
3. Adaptive Rank Test: Demonstrates that an adaptive rank test, which non-parametrically estimates the outlier distribution, attains the same local asymptotic power as an oracle test with full knowledge of the outlier distribution (Theorem 2).

4. Empirical Results

The method was evaluated on synthetic data and real-world high-energy physics data (LHCO 2020).

• Synthetic Data:

  • ACODE consistently outperformed individual-level identification methods (like Benjamini-Hochberg applied to conformal p-values) in terms of power for detecting the global null and providing informative lower bounds.
  • The adaptive selection mechanism successfully identified the best classifier (one-class vs. binary) and test (WMW vs. Fisher vs. Simes) for specific data regimes, approximating the performance of an oracle that knows the optimal combination.
  • In scenarios with "adversarial" outliers (where individual scores are under-dispersed and hard to detect), the data-driven approximation of Shiraishi's test significantly outperformed standard methods.

• LHCO High-Energy Physics Data:

  • Applied to 1.1 million particle collision events, ACODE successfully detected and enumerated "signal" events (outliers) against a background of simulated events.
  • The method provided tight 90% lower confidence bounds on the number of outliers, significantly outperforming the BH procedure in terms of informativeness.
  • Crucially, the adaptive version of ACODE achieved near-oracle performance without incurring selection bias, whereas a naive "cherry-picking" approach led to inflated Type-I errors.

5. Significance and Claims

The paper claims that ACODE offers a robust solution for collective anomaly detection where individual detection fails. Its significance lies in:

• Bridging the Gap: It connects conformal inference with classical multiple testing and rank test theory to handle weak and sparse signals.
• Principled Adaptivity: It solves the "selection bias" problem inherent in choosing machine learning models and statistical tests, providing valid inference even when the best procedure is chosen based on the data.
• Informativeness: Unlike methods that only identify specific outliers, ACODE provides a statistically guaranteed lower bound on the number of outliers, offering a more comprehensive view of the data's anomaly structure.

The authors note that while the method is powerful, it relies on the availability of a clean reference set of inliers and assumes exchangeability. Future work could explore cross-validation frameworks, handling contaminated calibration data, and developing faster computational shortcuts for the adaptive Shiraishi test.