On the Adversarial Robustness of Benjamini Hochberg
This addresses a critical safety/security problem for applications in drug discovery, forensics, and machine learning, revealing vulnerabilities in a widely used statistical method, though it is incremental in analyzing robustness rather than proposing a new paradigm.
The paper investigates the adversarial robustness of the Benjamini-Hochberg (BH) procedure for false detection rate control, demonstrating that its control can be significantly broken with relatively few test score perturbations, such as just one, and provides non-asymptotic guarantees on the expected adversarial adjustment to FDR.
The Benjamini-Hochberg (BH) procedure is widely used to control the false detection rate (FDR) in multiple testing. Applications of this control abound in drug discovery, forensics, anomaly detection, and, in particular, machine learning, ranging from nonparametric outlier detection to out-of-distribution detection and one-class classification methods. Considering this control could be relied upon in critical safety/security contexts, we investigate its adversarial robustness. More precisely, we study under what conditions BH does and does not exhibit adversarial robustness, we present a class of simple and easily implementable adversarial test-perturbation algorithms, and we perform computational experiments. With our algorithms, we demonstrate that there are conditions under which BH's control can be significantly broken with relatively few (even just one) test score perturbation(s), and provide non-asymptotic guarantees on the expected adversarial-adjustment to FDR. Our technical analysis involves a combinatorial reframing of the BH procedure as a ``balls into bins'' process, and drawing a connection to generalized ballot problems to facilitate an information-theoretic approach for deriving non-asymptotic lower bounds.