Testing for Outliers with Conformal p-values

Abstract

This paper studies the construction of p-values for nonparametric outlier detection, taking a multiple-testing perspective. The goal is to test whether new independent samples belong to the same distribution as a reference data set or are outliers. We propose a solution based on conformal inference, a broadly applicable framework which yields p-values that are marginally valid but mutually dependent for different test points. We prove these p-values are positively dependent and enable exact false discovery rate control, although in a relatively weak marginal sense. We then introduce a new method to compute p-values that are both valid conditionally on the training data and independent of each other for different test points; this paves the way to stronger type-I error guarantees. Our results depart from classical conformal inference as we leverage concentration inequalities rather than combinatorial arguments to establish our finite-sample guarantees. Furthermore, our techniques also yield a uniform confidence bound for the false positive rate of any outlier detection algorithm, as a function of the threshold applied to its raw statistics. Finally, the relevance of our results is demonstrated by numerical experiments on real and simulated data.

Revision May 24, 2022: added "asymptotic" and "Monte Carlo" conditional calibration methods; added power analyses; updated numerical experiments to include new methods

References in corpus (21)

• Deep Learning for Anomaly Detection: A Survey
• Robustness of multiple testing procedures against dependence
• Conformalized Quantile Regression
• Plug-in martingales for testing exchangeability on-line
• Predictive Inference Is Free with the Jackknife+-after-Bootstrap
• Uncertainty Sets for Image Classifiers using Conformal Prediction
• Generalizing Simes' test and Hochberg's stepup procedure
• A Power and Prediction Analysis for Knockoffs with Lasso Statistics
• Flexible distribution-free conditional predictive bands using density estimators
• Classification with Valid and Adaptive Coverage
• Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction
• PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction
• Cross-validation Confidence Intervals for Test Error
• Retrain or not retrain: Conformal test martingales for change-point detection
• Real-time Out-of-distribution Detection in Learning-Enabled Cyber-Physical Systems
• Exchangeability, Conformal Prediction, and Rank Tests
• Making learning more transparent using conformalized performance prediction
• Testing for concept shift online
• Bootstrap prediction intervals with asymptotic conditional validity and unconditional guarantees
• BONuS: Multiple multivariate testing with a data-adaptivetest statistic
• A Burden Shared is a Burden Halved: A Fairness-Adjusted Approach to Classification

Cited by in corpus (16)

• Conformal Prediction Under Feedback Covariate Shift for Biomolecular Design
• Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control
• Conformal Prediction using Conditional Histograms
• Root-finding Approaches for Computing Conformal Prediction Set
• Selective conformal inference with false coverage-statement rate control
• Sensitivity Analysis of Individual Treatment Effects: A Robust Conformal Inference Approach
• Selecting informative conformal prediction sets with false coverage rate control
• Conformal inference for random objects
• Conformal Anomaly Detection on Spatio-Temporal Observations with Missing Data
• Semi-supervised multiple testing
• Leave-One-Out-, Bootstrap- and Cross-Conformal Anomaly Detectors
• FDR Control for Online Anomaly Detection
• Data-driven Reachability using Christoffel Functions and Conformal Prediction
• Conformal novelty detection for replicate point patterns with FDR or FWER control
• Test for non-negligible adverse shifts
• Conformal prediction for uncertainties in nucleon-nucleon scattering