On the Adversarial Robustness of Benjamini Hochberg
Authors: Louis Chen
Roberto Szechtman
Matan Seri
Venue: NeurIPS 2024 poster (2024)
Keywords: multiple testing
p-values
false discovery rate
adversarial robust
Primary area: safety_in_machine_learning
TL;DR: As BH's FDR control could be relied upon in some critical contexts, we investigate its adversarial robustness via easily implementable, adversarial algorithms, and show that BH's control can be significantly broken with perturbations to few tests.

Abstract: 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.

On the Adversarial Robustness of Benjamini Hochberg
Louis L Chen'
Roberto Szechtman
Operations Research Department Naval Postgraduate School Monterey, CA 93943 louis, chenênps edu
Operations Research Department Naval Postgraduate School
Monterey, CA 93943 rszechtmênps edu
Matan Seri
Operations Research Department Naval Postgraduate School
Monterey, CA 93943 matan. wer. @eerri@@mmall.. com
Abstract
The Benjamini-Hochbert (BH) procedure is widely used to control the false de- tection rate (FDR) in multiple testing. Applications this control abound drug discovery, forensics, anomaly detection, and, in particular, machine learning, ranging from nonparametric outlier detection to put-of-distribbe one-class classification methods. Considering this control could be relied upon in critical safety/security contexts, we investigate its adversarial robustness. More precisely, 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 algorithmss, 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 adversarriallddjustmenn FDR. Our technical analysis involves a combinatorial reframing of the BH procedure a "balls into bins" process, and drawing connection to general- ized ballot problems to facilitate an information-theorfe approach for deriving non-asymptotic lower bounds.
detection and
Introduction
Multiple testing has broad applications in drug discovery, forensics, candidate screening, anomaly detection, and in particular, machine learning. Indeed, recent works [5]
28 32 in nonparametric outlier detection, ouitof-diitribution detection (OOD), and one-class classification have all adopted multiple testing methodology in developing principled decision rules with statistical guarantees. (BH) multiple testing procedure, widely used to control the false
[8
In fact, the Benjamini-Hocke detection rate (FDR), is either used or modified all these recent methods. Considering this FDR control could be relied upon in some critical (safety/security) contexts, for which false positives incur costs, we investigate its adversarial robustness.
Adversarial corruption presents a challenge to statistical methodology, and is modern concern due to not only the ease with which high volumes of data can now be accessed/processed but also the increasingly widespread use of statistical procedures. This threat poses vulnerabilities to machine learning tasks like OOD, which would aim to fortify security systems like fraud detection 5
webbsite: https://ouuslchhnngithhu github.io
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Manipulation of data and experimental results are common means by which incorrect conclusions can be reached. Worse, strategic perturbation can dramatically decrease the fidelity of the models and methods used. A burgeoning field of adversarial corruption has gained traction in recent years to meet this concern, most notably the area of (deep) machine learning; see, for example, [27 [27]1]] 20). In this work we address adversarial corruption in hypothesis testing, specifically in the large-scale context in which the primary focus is on the aggregate metric: FDR.
BH 6 is one of the most widely used multiple testing procedures, which upon input of a collection of p- p-values, outputs a rejection region ensuring that the FDR is no greater than a user-defined (0, 1). This control of FDR holds under independently generated p-values as well as some restricted forms of dependency like positive regression dependent on a subset (PRDS) [ - but it generally holds without strong assumptions on the alternative distributions. This degree of distributional robustness, however, could be said to come at the cost of adversarial robustness, as we show in this work.
threshold
1.1 Literature Review
Although OOD methods 12 21 [2) are often complex and not always supported by statistical guarantees, conformal inference has made possible the use of one-class classifiers to generate conformal p-values for which OOD can now be conducted via multiple testing. This has led to the adoption of the BH procedure in OOD. Indeed, [5] leverages the FDR control afforded by BH over conformal p-values (shown to be PRDS) to test for outliers. More precisely, given test set of observations for which we wish to identify as inliers or outliers (out of distribution). a conformal p-value is generated for each observation, which is then processed by BH to decide which are likely outliers. We refer the reader to
for other recent works along this vein.
In recent years, concerns have risen over the possibility of adversarial manipulation of statistical methodologies. This manipulation commonly occurs at the level of data collection and training, often invalidating the assumptions made regarding how data is drawn, but it can also occur at test time. There is growing literature on adversarial robustness, which is concerned with securing statistical methods like (deep) machine learning [27 16, 20), linear regression [8), M-estimation [9], and online In particular, [33 considers contamination models that incorporate (adaptive) adversarial perturbation of up to an c- fraction of drawn data. Indeed, we adopt this modeling in our own study see (c-Perturb). As well, a similar concept to the notion of adversarial robustness that we adopt in this paper is one the literature refers to as perturbation resilience. Generally speaking, a problem instance is called a- perturbation resilient when despite a degree (parameterized by a) of perturbation to the instance, the optimal solution does not change. First introduced in [TO] for combinatorial optimization (in particular, MAX-CUT), the concept has since also inspired research
learning 26
into devising resilient unsupervised learning, particularly in clustering 4 3.
With respect to the hypothesis testing literature, there are recent adversarial robust studies focused on simple [19] and sequential hypothesis testing [TT] from a game theoretic perspective, in which protection of statistical power, risk, or sample size from corruption of chief concern. Comple- menting the adversarial robust perspective are several distributionally robust studies, in which the data- geteraeneratigg distribution is known only to lie in a parametric family. Recent works include which focus on test risk in single and sequential hypothesis testing settings employing uncertainty sets of distributions of fixed distance (e.g. Wasserstein, phi-divergence) for the null and alternative hypotheses. In contrast to these works, this paper is focused on FDR, not individual test risk. Furthermore, distributional robustness is not equivalent to the cnrturbation-robusnee paper and other adversarial robust studies seek in general. Indeed, [30] shows that the BH procedure's 's FDR control exhibits a distributional robustness to possible dependence between null and non-null hypotheses. On the other hand, our work would illustrate that, distributional robustness aside, BH can lack adversarial robustness.
I1 24 [5]
that this
1.2 Preliminaries
We (I,...,N) N). where N E Z. finite set for which each member i e V denotes a binary hypothesis test deciding between null and alternative hypothesis. Further, there exists a partitioning. N Ho u Hi, such that the correct decision for test E W is either null if e Ho. or alternative i E Hi. Here, Ho and Hi are the (unknown) sets of null and alternative test indices, respectively;
2

---

consequently, for any test i, the correct decision (i.e. set membership) is unknown to the decision maker. In fact, while the number of tests N is known (and large. on the order of thousands), neither is known to the decision maker, although To 2 0.90 "is reasonable in most large-scale testing situations" (04), p. 285).
No |Ho] nor To
For each test i E N, p-value p. [O,1] is randomly generated (independent of all other Pj. j i), which we model as draw from either U(0, 1) when No (p; then referred to as a null p-value) or some alternative distribution PP on [O, 1] when E Hi (p: then referred to as an alternative p-value). A multiple-testing algorithm A takes as input randomly generated collection of p-values p {pihie and outputs for each test determination A(1) {0, with A(1) 1 iff the determination is to reject the null hypothesis (i.e., claim i E H1). or sometimes referred to as "make a discovery" for the i-th test. With ap := Eier. A(i) denoting the number of false discoveries, and Rp == [A (1) denoting the number of rejections/discoveriee made, refer FDP[A:p] v. as the false detection proportion summarizing A's decisions on p-values p, where T is shorthand for max( y) for any x, y e RR We refer to its expectation with respect to the random generation of p as the false detection rate, FDR(A)= == E.DA:p::
dp
In this work, we focus on the Benjamini Hochberg procedure, widely-used multiple-testing algo- rithm.
1.3 The Benjamini Hochberg (BH) Procedure
Given collection of p-values p {pi)iav and desired control level q e (0, to bound FDR, the BH procedure BH, operates as follows:
1. The p-values are sorted in increasing order, P(1) $ P(2) ... S P(N)
2. The index imax == max [O,N]z P()) $ $ is identified, with P(o) := 0.
3. Reject the tests corresponding to the smallest imax p-values: P(1))P(2):-- ........... P((
BH, provides provable FDR control at the level of q without any assumptions on the alternative distributions [P]]
Lemma 1.1 (Theorem 4.1 from 14). If every null p-value is super-uniform, equiv, p; ~ PP UO0, for for all & Ho, and the collection is jointly independent, then regardless of the collection of alternative distributions {P]
FDR(BH,) = Too S g, Vq (0,
Remark 1.2. In fact, the assumption of joint independence of the null p-values can be relaxed to form of dependency known as PRDS see 7 for this generalization of Lemma 1.1
1.4 The Adversary and the e- c-Perturbation Problem
We model an (omniscient) adversary with knowledge of Ho. Hi, and that knows the decision maker's choice of control level q. The adversary receives the p-values p = (p.) after they generated but before they are received by the decision maker, or before test time. Given the ability to perturb c 2 1 p-values, the adversary solves
max p'ill-pp lose
FDP(BH,:P',
(c-Perturb)
where p' denotes the p-values derived from an adjusted collection of p p-vuuues p' (p)) i=1 In words,
the adversary finds the perturbation of at most c-many p-values before the execution of BH, as to maximize the ieversariall-adjustee false detection proportion F FDP[H p']. p-values is implicitly the result of data perturbation, and we refer to both Remark 4.6 and Section 5.2 for examples and experiments involving direct perturbation of data.
Perturbation of
While we assume omniscience for the adversary throughout, we will briefly address modifications in analysis for an oblivious adversary that has no knowledge of Ho, nor Hi. Indeed, our algorithms to be presented can be modified naturally for implementation by an oblivious adversary (see comments in Section 3 further, there nearly equivalent performance when mo large, as is typical. Hence, is for the sake of brevity that we omit explicit analysis of the oblivious adversary.
3

---

1.5
Main Results
Intuitively, the effect of a small number of p-value perturbations becomes insignificant in settings where large number of tests are rejected (see Theorem (.2). This happens, for instance, when either the number of tests N, or the control level q. or the distance (e.g. KL-divergence) between the null and alternative distributions, is large. For this reason, we focus on results that are non-asymptotic in the number of tests N.
In Section 3] we present the algorithm INCREASE-c that uses strategic increases to c null p-values to induce expansion of the BH rejection region. We also present efficient, optimal algorithm MOVE-1 (Appendix Section
7.2) for the adversary's 's maximization of FDR with at most one (i.e. c= 1) p-value
perturbation.
In Section 4 we discuss the adversarial robustness of BH through study of the adversarial adjustments to FDR by the INCREASE-c algorithms, revealing where its control is and isn 't adversarially robust.
In Section we provide accompanying numerical experiments on i.i.d, as well as PRDS p-values.
2 BH Balls into Bins
In this section we will establish important notation for the discussions to follow. We reduce the real line collection of N + "bins". No and N1 balls will each be assigned independently of each other, from discrete distributions that are specified in the next subsection. The main motivation for this reduction is to facilitate discussion of effective perturbations in Section 3 and for the technical analysis in Section
of these bins
2.1 The Balls into Bins System
We partition the segment [0, 1] into N equiprobable segments that will be referred to as bins. We define the i-th bin B; := (p e IR (i-1) sp< / for = ,,...,N. N. What remains forms bin N 1, i.e. BN+1 == {p& E R 2:12p2 - For shorthand, we write B == uj_1 Bi = {pe R: :R:0pp< i Finally, write Dd : |B, n (pr and B. == [B, {pr for bin i's, respectively, null-load and total load. The alternative- load B, is defined analogously, are By B and B
Borrowing terminology from the classic balls into bins problem of probability theory 229. this framework facilitates re-interpretation of the random drawing of p-values as balls being randomly placed into an ordered collection of bins, enumerated up to N + Framed in this way, we see that B Hg operates by identifying the rejection count
Rejection Count:
x= = max i E N0, B
which corresponds to the largest collection of consecutive bins 1...., i that collectively contain precisely balls, so that BH, rejects all tests with p-values lying in the first bins. The case = 0 corresponds to rejecting tests. In fact, l is stopping time under filtration F that define next.
Filtration F No: Let [0, 1 be a sample space with the classical Borel algebra and (with slight abuse of notation) probability measure := (#Ie,, 1)) (@seH, We define a filtration beginning with Fx := a (BB (BBN B 1) and continuing inductively (N towards 0), N++1 let F, be the o-algebra generated by (BA j--i+1 and { {B9) N+1
fj-i+1- In words, this filtration corresponds to what is cumulatively learned about the bin loads (null and total) upon examination of the bins in sequence starting with bin N + and concluding with bin 1, assuming each observed p value comes with correct identification of whether not i Ho.
We note the fact that for > i, follows that F BO
F2
B a.s., so that
Bi form a martingale sequence adapted to the filtration. This fact will prove useful when combined with the optional stopping theorem facilitate several results in this work.
B
Bd B N N-1 .....
Under this lens, the adversary's 's (algorithmic) task reduces reshuffling p-values among the bins, and in Section 3 we demonstrate there are indeed simple, tractable ways of performing this to manipulate

---

BH. with potentially great effect on FDR control. The key insight is that there exist alternative stopping times that present alternative rejection counts (/regions) that can break FDR control.
3 Adversarial Algorithm: INCREASE-c
Throughout this section, we don the role of the adversary and study the[c-Perturbpprol problem, in which are given g e (0, 1). realized collection p (pi (along with the labels of null or alternative for each pt), and a budget 2 1, and our task is to produce a perturbed collection y'. Toward this, we focus on a procedure called INCREASE-c that despite its sub-optimality (see Appendix Section 7.2) is intuitive and simple to execute; further, as theoretical and empirical analysis in sections and respectively show, has strong performance in expectation.
We begin by defining a random variable that is a stopping time adapted to F; given an integer c 1, let
max [c,N]z BY -
B 2 c
Ric ==
(3)
k
B <
and we choose to write k, in place of k,1.
Increasing the Rejection Count The interest in ktc is that if we moved any selection of null p-values from bin N + 1 into bin ktc (in fact any bin i s k.c), then BH, would output a new, increased rejection count kec- We formally study this in Section 4 In the meantime, comment the increase ktc- k. which is a difference between two stopping times
It is easy to see that k - 2 c whenever x hence, the increase in the rejection count is at least e, but possibly more. We provide stronger lower bound on this increase by utilizing the ratio between the number B k+2.N of nulls not rejected by BHg and the number - (1: + 1) of bins left outside of the HH, rejection region the case of corruption. Computational experiments indicate comparable performance of this bound with those of simulations presented in Section 5 Table 1
Theorem 3.1. If 1, then
E [ KIIL N+1 20}2
+1
(4)
B LonN
1-
||
B
2
N-(k+1)
for any collection of alternative hypothesis distributions {PP
INCREASE-c runs as follows:
1. IF B 2 then move the largest (ties broken arbitrarily) in the (N+1)-th bin to bin kic-
2. ELSE leave the p-values unperturbed.
fact suffices for the c-many p-values to be placed any bin i kec. We remark that since an oblivious adversary cannot discern null-draw from alternativedrawnn in the collection INCREASE- с as written is unimplementable in such a case. Hence, for the oblivious adversary, we modify INCREASE-c's criterion to BY1 p-values uniformly at random from among the p-values in the (N 1)-th bin. Intuitively, this modification for the oblivious adversary should yield nearly null p-values being moved (on average) just as the non-oblivious case, assuming the proportion of nulls among the B many p-values is high, as a typically large To would entail.
and have the oblivious adversary now take the c-many
We conclude this section with characterization of the average increase in FDR, denoted A. that INCREASE-c induces.
Theorem 3.2. Given e 1, let pwc denote the perturbed form of p that INCREASE-C produces. Then the adversarially-adduseee FDR induced by INCREASE-C is
BFDP(BH,;Ptda EEDPPBB + Ac.
for any collection of alternative distributions' ( (P]), where
Ag
BQ
(5)
5

---

In Section to follow, we provide analytical lower bounds for A. as part of discussion on BH's adversarial robustness. Section presents computational experiments (e.g. Table D. We remark that INCREASE-C is not optimal for all instances of C-Perturb) indeed, for c 1, we present
provably optimal algorithm MOVE-1 in Appendix Section 7.2 which in contrast to INCREASE- I sometimes induces a reduced rejection count. However, INCREASE-c remains a formidable adversarial procedure, as the results of Section demonstrate on not only i.id. p-values but also PRDS conformal p-values.
4 Theoretical Analysis: Performance Guarantees and Insights into Adversarial Robustness
is (distributionally) robust in the sense that it holds no matter the alternative distributions { rieH, However, as Theorem 3.2 indicates, the degree to which this control can withstand data perturbations at test time, i.e., its adversarial robustness, very much depends (P) heess
BH's FDR control - Lemmaa I.I
Recalling Lemma 1.1 we may assume without loss of generality that no alternative distribution IP! stochastically dominates UO0 1) (equiv., P, (0, 1)). That being said, the "degree" to which the alternative distributions {P)) le are (stoch.) dominated by the null distribution U(0,) 1) (equiv.,
P & (0, 1)) is critical. We briefly preview two regimes of special interest for which each of the next two subsections cover.
High sub- uub-uniformity: When the alternatives are sub-uniform P. & UO0, 1) for all i E H1, and highly so, such that for all E Hi it holds that P! (p. < e) x for some small > O, then it follows that is large and Big should contain most alternative p-values. Consequently, in order for INCREAES-C to induce any sizeable increase to the FDR, the adversary will need to expand the BH rejection region significantly as introduce commensurate number of nulls. Table I indicates may need to be quite large to make a dent in FDR control. This message is made more precise in Theorem 4.1
Low sub-uniformity: As we will see, when the alternative p-values are barely dominated by U(0, 1), Ae can be rather large. In fact, the special case that there is no dominance such that PP (O, for all i E H1. a strikingly vulnerable state occurs with high probability. Indeed, in this case where nulls and alternatives are virtually indistinguishable, BHg (in fact any A) admits an FDR of To whenever any rejections are made (i.c., E [FDP[BH, plllk: 2 1 To) so that BHg accordingly compensates by making rejections with high probability (IP (k 0)
2). which follows by the distributional robust control |I from Lemma 1.1 But those times when = 0 is precisely when INCREASE-c's simultaneous expansion of the rejection region and injection of nulls into this region is most damaging. That this event and other similarly vulnerable events occurs with high probability is the fault of the distributional robustness. This message made rigorous in the forthcoming Theorem 4.5
4.1 Case of High Sub-Uniformity in Alternatives (TP))
IP & (0, 1) for i Hi, with P (p; <e) x for some small > O, then it clear that the num- ber of alternatives rejected by BHg should be nearly the maximum number N1 of correct rejections possible (i.e., B = N2) with high probability, limiting any potential impact of INCREASE-c.
The following bounds are formulated to elaborate on such dynamics in this case of large separation between alternatives and nulls, for which the event [B] Ni] has probability close 1.
Theorem 4.1. If 2 1, then
A. s P (B). N))
e
BBy 20 +1-P(B). N1)
c+ Ni + B 1NN++e
and
(N₂ + c) IP (B). = N1)
I.. krc B N 2c}2
(6)
1 EB
P B0 I:N S No

---

In words, for fixed as the alternative distributions concentrate more and more on 0, it follows that IP =B f 1, so that the effect A. of INCREASE-C on BH's FDR is dampened. And this occurs despite the fact that the increase h k in rejection count produced by INCREASE-C consists of mostly the introduction of nulls, and tends to magnification of (Ni + c) by at least
B | S No -N-cc.. which is straightforward to compute since c].
a factor of the inverse of 1- E
N
BiNN Binom(No.q) We refer the reader to Section 5 Table 1 for simulations illustrating the
above.
4.2 Case of Low Sub-Uniformity in Alternatives (P)))
In the study of this regime, we aim to demonstrate that the adversarial increase A, can be rather large. We provide a lower bound Lee on Ac that will be function of parameters q, N,, No, as well as the alternative distributions {PP Ne96s.
4.2.1 Lower Bounding A.
In view of 5 the event [ksc = cl is clearly of significance in the computation of A.. In words, this event describes the case that the BHg rejection region captures nothing, and yet when the adversary successfully executes INCREASÉ-C the rejection will now capture only nulls generating a false detection proportion of 1. Hence, we lower bound the adjustment A. of Theorem 3.2 by lower-bounding the probability of this event.
Our strategy: (1) first, characterize this probability under the special case that P = (0, 1) for all i E H1: (2) second, to handle when P! x (0, 1) for some i E H1, we translate the KI. divergence of the resulting discrete, bin-assignment distributions into bound via Pinsker's Inequality.
The key to the first step will be to recognize that when P: (0,1) for all i е Hi, the vector of total loads (BN ..... B is exchangeable (i.e., its law is invariant under permutationns) given B Indeed, exchangeability, combined with the generalized Ballot Theorem of [31 yields the following result:
Corollary 4.2. Let 2 1, p E [0.1], and x a non-nigative integer such that 0 s S If
B = (BI....,BB) Ba) ~ M Mullinomial x, (p....,))), p)). then IP (n" [-: B, r))
=
Armed with Corollary 4.2 we can begin to estimate the probability laws of k and kec.
Corollary 4.3. Pf : U(0, 1) for all Hi,
then P (is = f) = 1-gt (N-Da
1-9
PP (B = for ビ N, where 0o 1,
and TP (BN. = =) (7) (gl)
(1 x N-C.
If B c, then IP (kre =
1) -1- (4) NO N1 +) No 1 (1 No- B&g
Nig
N
N N-eg
Next, we carry out the second step of our plan. Towards this, make the following assumption. Assumption 4.4. Suppose the alternative p-values are independent and identically distributed,
with common distribution PP, i..., {p.)iet, sid PP. We write 8 := (1 9) PP' (p, BN-1), and 5y = I (pr B,)- - $. and we assume that Ip' (pr e B₁) > O for all j E [N]. as well as P2 (p, BEN) 0 for arbitrary { N.
This assumption not only reduces the notational burden (otherwise documenting N1 many alternative distributions) but also allows the leveraging of KL divergences between the different bin assignment distributions implied by the alternative P' versus the null UO,, 1).
Theorem 4.5. Suppose Assumption 4.4 Then
N1
[11
) No (1 (1- -V. Vo)Me - Ze]
A Lalg, N, No, P2)= : N
81ze
where
N, N, Eo+ B BL.-0
E [ [B] 0] =N, (N-1)
N-c
N-c4- No
V.lg. N, No. Pt) :=
in2 F. B1
B1 1.c = 0] DK (PI,c)),
7

---

N, = N-1.
IB 2) 1/-11 B sc-
N-C
1 B B
No) := P 2c) (1- N)
N-c
(TI(PP' ,c) Σ, No g+ Ei- (g-11((
(N/o1//N++;))
Remark 4.6. For a more concrete application/example, consider when the p-values {pi ken are derived from z-scores heN via P. (Z 2,), where Z ~ (O, 1), with null z-scores EijieH ii.d. (O 1) and alternative z-scores (z; [at, i (with all p 0). Indeed, under this framework, we may view the j as the distance between P, and (0, 1).
Towards satisfying Assumption 4.4] we can assume throughout that there exists a nonnegative pa- rameter A1 such that the alternative parameters (p),o') = (#1.1) 1) for all i H4. Indeed, if every member of the collection (μi JieH, is in reality only close to zero, then the forthcoming estimates (lower bounds) would provide close, conservative estimates when setting μt = max(u² : Hi}. (1-9))- 0. As well, 63 (x1) := When 111 it follows that 6(11) (1 9) ②
01
+ (1-12-11 1-1
4 (1-1
N. Intuitively, BH adversarially robust (A. small) when the alternative distributions are "far" (/1 >> 0) from the theoretical null, and the opposite holds when they are "close" (/1 0)- Figures and 3
5 Simulations and Data Experiments
In this section, we provide computations (performed in and Python on a Machook Air-M2 chip, 8GB memory, with experiment time exceeding minutes) to demonstrate the performance of the adversarial algorithm INCREASE-c. We demonstrate its performance through simulation on synthetic data to make comparisons the theoretical estimates provided in Section 4 We then demonstrate its performance on a real-data experiment in outlier detection.
5.1
INCREASE-c Simulations on Synthetic Data
5.1.1
INCREASE-c Simulations on i.idd. p-values
Following the framework from Remark 4.6 we simulated 10t replications of the following experiment: (1) 1000 p-values are generated, with {piliens sēd U(O, 1), and each p; among {p: Jani gen- sid
crated via p; = 1- Φ( (-=#)), ), with {ai) N( 1); (2) FDP[BHHiPP p] and FDP[BH, P pairs are plot- ted. As can be seen, the vast majority of the pairs satisfy F PPe] FDP [DP((H, and, further, all pairs lie above the horizontal line situated at the level of the BH control level mo q .09, ie,, F FDP[ [H Ptee] #0 q-
are calculated. In Figure each of the 10* many (FDP(BH,;1) p) HDP[BH,;;Pe
In Table [ we present the effectiveness of INCREASE-c over ranges of corruption budget e and M1 from small to large. As can be seen, when μ1 = O, any amount of corruption budget yields large port-corruption FDR E, [ 2+e]. When μ4 0 grows, however, the budget must correspondingly grow in order for there to be nontrivial post-corruption FDR. Finally, note that for any fixed the increase in rejection count k.c Æ is the average larger when μ1 is larger. For experiments on non- i.i.d., PRDS p-values, we refer the interested reader to Section 5.2 or Appendix Section 7.4
5.1.2 INCREASE-1 Simulations versus Theoretical Bounds Under Small μ41
In Figures and 3 we illustrate how well the insights discussed Section 2 capture the sensi- tivity of BH to adversarial perturbations when b1 is near O. Specifically, for each in the grid .99]. ....,.0.......... we computed the difference F FDP[BH,; p+ FDP BHy p] across 10 repli- cations of the setup in Section [.1.I with the average of this difference being an estimate of A The plot of these A estimates with respect to is then compared with the plot of our lower bound L1 as function of q.
Figures and 3 illustrate that the stricter the control, i.e., the smaller q is, the more effective INCREASE-C becomes. In fact, the bound indicates high vulnerability for the typical use case
8

---

Simulation of INC. R. ASE -10
Nu-002, Mym230, q 2.12, uu-2, #Sinuasoors +Ic4
Frequency
A1
0
2
1000
1
99 (1.11)
(1.39
.1.9
2
.99 (2.22)
.77 (2.75)
(3.7)
5
(5.6)
81 (6.67)
.66
10
.99 (11.22)
(13.76)
36
100
.99 (111.30)
91 (121488
.72 (136.2)
01
60
200
.99 (222.41)
.33 (237.78)
.81 (256.0)
500
.99 (555.59)
.55 (580.75)
.89 (601.5)
BHF botre Advesory
Figure 1: 10 simulations FDP by BHg before and after INCREASE-10 is executed on the p- values. N 10', No 900, and y 0.10.
Table 1: Sample Average (10*-batch) estimates of EFFDDP(BH Z+c] and [ (in paren- theses) when all { je commonly equal some je {0, 2, and N 10 0.10, no 0.90, and all of = =1.
0226
Levela
Contco Level
Figure 2: Comparing the FDR increase A of INCREASE-1 with the lower bound L1 of Theo- rem 4.5 as functions of q when μn 0, N 1000
Figure 3: Comparing the FDR increase A of
INCREASE-1 with the lower bound L1 of The-
orem 4.5 functions of g when μi .25,
N 1000
of g (0, 0.1).. On the other hand, as increases, INCREASE-c's effect weakens; however, for increased g, the decision maker is accepting higher FDR already.
5.2 Real-Data Experiment: Credit Card Fraud Detection
The Credit Card dataset D {(X,, YO) S 30 (0,1) contains 284, 807 credit card transactions September 2013 by European cardholders over the course two days 492 which were frauds. Each X, RR consists of numerical input variables that are the result of PCA transformation. The "Class" label Y, takes value 1 in case of fraud and 0 otherwise (/genuine), yielding the partition [m] ng n1. with Ino 284, 315 and |n|| 492.
Fraud Detection Experiment
Given a set of unlabeled transactions {Xishees where S [r2]. the fraud detection task is to identify which members
belong to nı, i.e., are fraudulent. We experiment with the BH-based, outlier detection method of [5] on this fraud detection task specifically, we consider the false detection proportion of this method the absence and presence of adversary. The details the experimental setup will now be discussed.

---

Training
We begin by training unsupervised decision-tree based algorithm on training set. From the set ny of genuine transactions, we uniformly random select subset Petrain no of size 141, 758 to form a training set Deroin iemerenaaa ienerasn upon which we train isolation forest [25] 8 IR30 R. using the R library isotree where, in principle, s(X;) returns an isolation depth that is smaller if Y = (i.e. is an outlier) and larger if Y, 0 (i.e. an inlier)
Calibration and (Adversarially-Pertuue
Testing
Then for each of 10 simulations, we uniformly at random selected subset New! S Ro > Tetrinn of size 141, 657 to form calibration set Deal := {X;))een (ennaa of strictly genuine transactions. As well, we uniformly at random selected a subset Reest,1 S nu 100 fraudulent transactions to append to the 900 remaining genuine transactions comprising Ritet, == no Rerain Recal to form test set transformed X; P; (0,
Diest := (Xieeen where 7oeeat Atestt, U Rlteat11. Finally,
for each i Viasst via Pr ( (x))sx(X)) The resulting collection of conformal p-values Reaat
(p: (Pi)iefeas is PRDS, as proven in [5], and hence the FDR control of Lemma 1.1 holds (see 77.. In contrast, upon executing INCREASE-C to generate a corresponding adversarialyy sentanially-ertuubber collection P+o ieffess obtain a collection for which BH's FDR control longer holds.
Experimental Results
We executed B Ho.1, on both and p-c. with an execution providing the decision for each Atest whether report it as genuine (null) fraudulent (alternative). We report the average (over the 102 simulations) false detection proportion (FDP) produced by B i.c., both I (o. Ho.1;p and E FDDDP( [B..H.HH. 1; P.e]] (for e 1,5, 10). As well, we report the average number of alleged
frauds E k and IE [+c]. As Table indicates, although the method of [5] can ordinarily control the
c
E
BF
E[FDP BH, p+c]
E[k]
E [
.09
.10
60.21
60.21
5
.08
.17
48.69
57.12
10
.09
.23
56.39
72.85
20
0.09
0.31
58.12
89.06
Table Credit Card Fraud Detection Experiment
FDR below the explicit 0.10 level, INCREASE-c has the ability push the FDR above this control level.
6 Conclusions
This is the first work to consider adversarial corruption of the popular Benjamini Hochberg multiple testing procedure to break its FDR control. While BH may exhibit robustness when the alternative distributions are "far" from the null, it exhibits great sensitivity in practical cases when the alternatives are "closer" to the null. In such cases, with the modification of few p-values (as few one), the attacker can increase the expected FDR well past the guarantee stipulated by the BH procedure. This study suggests some caution may be necessary when using BH. especially in safety-securit settings. Numerical experiments support the analytical results. Finally, BH is but one member of the family of step-up multiple testing procedures, which generally entail rejection regions decided via stopping time, which since our paper shows can be manipulated in the case BH, it means other step-up procedures be similarly prone.
hntrrooiiiieeeessstnantonnctttoo Introduction Isolation Forests.hie html
10

---

Acknowledgments and Disclosure of Funding
We wish to thank Wang Chi Cheung for a stimulating conversation. This work was supported by the Air Force Office of Scientific Research (Mathematical Optimization Program) under the grant: "Optimal Decision Making under Tight Performance Requirements in Adversarial and Uncertain Environments: Insight from Rockafellian Functions".
References
[1] Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33:14315-11422 2020.
[2] Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev. Algorithms for stable and perturbation-resillen problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1384451,27 2017.
[3] Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Information Processing Letters, 112(1-2) (2111-2))995555) 54, 2012.
[4] Maria-Florina Balcan, Nika Haghtalab, and Colin White. K-center clustering under perturbation resilience. ACM Trans. Algorithms, 16(2), mar 2020.
[5] Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. The Annals of Statistics, 51(1):149-178, 2023.
[6] Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: practical and powerful approach to multiple testing. Journal of the Royal statistical society: series (Methodological), 37(1):289-300 1995.
[7] Yoav Benjamini and Daniel Yekutieli. The control of the false discovery rate in multiple testing under dependency. The Annals of Statistics, 29(4): 16111118555 2001.
[8] Daniel Berend, Aryeh Kontorovich, Lev Reyzin, and Thomas Robinson. On biased random walks, corrupted intervals, and learning under adversarial design. Annals of Mathematccs and Artificial Intelligence, 88:887-905, 2020.
[9] Sujay Bhatt, Guanhua Fang, Ping Li, and Gennady Samorodnitsky. Minimax m-estimation under adversarial corruption. In Proceedings of the 39th International Conference on Machine Learning (ICML), Baltimore, MD, 2022.
[10] Yonatan Bilu and Nathan Linial. Are stable instances easy? Combinatorics, Probability and Computing, 21(5):643-660, 2012.
[11] Shuchen Cao, Ruizhi Zhang, and Shaofeng Zou. Adversarially robust sequential hypothesis testing. Sequential Analysis, 41(1):81-003 2022.
[12] D.Hendrycks and K. Gimppll. A baseline for detecting misclassified and out-of cuttof-diisrrbution examples in neural networks. In Proceedings of International Conference on Learning Repre- sentations, 2017.
[13] Ilias Diakonikolas and Daniel M Kane. Algorithmic high-dimensional robust statistics. Cam- bridge university press, 2023.
[14] Bradley Efron and Trevor Hastie. Computer age statistical inference, 2013.
[15] Rui Gao, Liyan Xie, Yao Xie, and Huan Xu. Robust hypothesis testing using wasserstein uncertainty sets. Advances in Neural Information Processing Systems, 31, 2018.
[16] Ian Goodfellow, Patrick McDaniel, and Nicolas Papernot. Making machine learning robust against adversarial inputs. Commun. ACM, 61(7)556-66, jun 2018.
[17] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference Learning Theory, pages 1562-1578. PMLR, 2019.
11

---

[18] Ying Jin and Emmanuel Candès, Selection by prediction with conformal p-values. Journal of Machine Learning Research, 24(244):1-41, 2023.
[19] Yulu Jin and Lifeng Lai. On the adversarial robustness of hypothesis testing. IEEE Transactions on Signal Processing, 69:515-530, 2021.
[20] Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert Schapire. Contextual search in the presence of adversarial corruptions. Operations Research, (1):; 120-1135, 124::1120-:1335 2023.
[21] K. Lee, K. Lee, H. Lee, and Shin. simple unified framework for detecting out-ofdistribution samples and adversarial attacks. In NeurIPS, 2018.
[22] K. Lee, K. Lee, Lee, and Shin. Training cifeddence-calbbatte classifiers for detecting out-of-distribution samples. In International Conference on Learning Representations, 2018.
[23] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
[24] Zishuo Li, Yilin Mo, and Fei Hao. Game theoretical approach sequential hypothesis test with byzantine sensors. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 2654-2659. IEEE, 2019.
[25] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In 2008 eighth ieee international conference on data mining, pages 413-422. IEEE, 2008.
[26] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 122, 2018.
[27] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[28] Akshayaa Magesh, Venugopal V Veeravalli, Anirban Roy, and Susmit Jha. Principled out-of- distribution detection via multiple testing. Journal of Machine Learning Research, 24(378):1-35, 2023.
[29] Martin Raab and Angelika Steger. "balls into bins" simple and tight analysis. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 159-. 170. Springer, 1998.
[30] Weijie Su. The fdr-linking theorem. arXiv preprint 1rXiv:1812.08965. 2018
[31] Lajos Takáes. A generalization of the ballot problem and its application in the theory of queues. Journal of the American Statistical Association, 57(298) 1962.
[32] Weiwei Liu Xinsong Ma, Xin Zou. A provable decision rule for -ustr--dist detection. Proceedings of the 41 International Conference on Machine Learning (ICMI), Vienna, Austria, 2024.
12

---

7 Appendix supplemental material
7.1 Adversarial Algorithm: INCREASE-c
Theorem 3.1. c 1, then
E E[ke K 2c]2
B
1-E
B 20
N-(k+1)
for any collection of alternative hypothesis distributions [PP
Proof. Since the statement in the case of is trivially true, henceforth assume that c 1. Recall k,c max [c, Mz Bia i c). Let define ki == max{i [c, Iz Bß. = -- + c)}
Then begin by establishing that
hic kic > k
To see why this holds, we note that Bd Bh = k - B1 iik1 = (B) + +1) k + - 1 1i+1 + C),
litt
and this implies h: + kif- Further, B1ggg
1:kg
+ BBig.
= 1.0
(B)
1sk c) + B
1:k2
ko -+ (B) Like. B1x) ko c, which implies kic k4c-
Next, we justify the relation
B K+2NN
B
2+222
E
|l k B
[B c = IE
k B [B
11+
7:0
(Is +
It suffices to establish for any fixed, joint realization of k. Bix that occurs consistent with the event [B 2 c] with positive probability. With slight abuse of notation, we will continue to use k B! 1:k for such a fixed realization, and write E. for E [-[ B! I-E. [B c]]. The plan is to apply the Optional Stopping Theorem on martingale sequence. To so, let us form a (backwards-rumning filtration: let FN be the sigma-algebra generated by the event [B 2 c] as well as the random variable 1. and let F, be the sigma-algebra generated by the event [B 2 c] as well as the N+1
random variables {B j- Then for any integers k, 5, (N,N 1, 1,...1) ... such that &> k,
[k (k]+
I.. Bi
(
F
F. 2-2((((()22)
[
||
(12((((())
[E (k+ 1)] 2)=((((()))))
where B (-2(ev(k+2)) Fe since B
B (+2(00((+22) No B
(k- B B (e+1)v(R+3)aN is Bo 2-2(we(-2))
measurable function of the random variables in Fe. In other words, the collection {
(K-((++)]vv
forms martingale under the filtration. As well, 2y is stopping time. Hence, by the Optional Stopping Theorem,
B B N 1k+1)
BD
E
|| k, B1 180 [B
cc
K-2:N
[B cc]
N
11+
B"
B
E
k+2:50
||
[Ba c]
k-2
|| k B), [B% 20]
(k (
1.0
(k+1)
We note that the martingale property could be established even without the event [B c] in the filtration but for the sake of forthcoming computations we have included it.
Next we observe that
B0 b4220 + k +k-B), = B k+20g + -000 Ligg = =ko -B1) + cc)
Bh Blrzke = =ko (Ts c),
13

---

we derive
Bo
k+2:k0.
10 (k+c)
20 - 1) c
=1 c-1
K.c (k +11
koce - (k (k+1) 1)
- (k 1)
h4c - (k+
B
0<
K+2:N
k.
B
[B N+1 2 c|
= (c 1)
K lik. [B 2 2c]
<1
N (k+1)
lik
ho - (k+1)
1
|| k. B 1:k: [B 2c]
E
R0
(k + 1) k. B¹
[B N+1 c]
h (k: 1)
1:k
Bingin N-(k+1)
1 F
k, B1
[B N-1 2 cc]
lnke
C-1
Hence,
c-1
+1 EE No - k B Isk
[Bx,, 2 2c] s EE [h.. - 1 B.B. [B 2 cc].
1
FaRyy N (k-1)
|| h Ba 1ik
[B 2c]
follows that
C-1
C- 1
+1=
+1
E
E+2N (k+1)
||
Bo N+1 2
EF
E+aN N-(K+1)
||
k B1 1:k
[B cc]
|| B 2
EE
C-1
|| B N+1 2
21
+1
B E-2:N N-(k+1)
1 IB
k
B1 1ik
1B 2 2c]
S IE k.c k || BN 2 cc,
where have used (conditional) Jensen's Inequality valid because and (*) ensures 1 || k B. 1:k [B2-1 2 el] < >0.
B
E
N-(1-1)
Theorem 3.2. Given c. 2 1, let p-c denote the perturbed form of that INCREASE-C pNCREASE-cproduces Then the addverarially-adjuseee FDR induced by INCREASE-c
BFD HEF Ac.
for any collection of alternative distributions (TP! where
A =
B 2 c
(5)
kin
Proof. We derive
(TDP|BH,gP... E
B
liken
+c
BB 2
+ EE
B
l:vvl
Ba <
hic
kvi
B
B30
E
likse
B 20
+E
1
2
+E
11kv1
B
B <c
kic
K+c
kvi
PP (B 2 20
E
B00
i:N
B
2 c
+
+
c
2
+
(B%
<c)
EE
B
B%
cc
N
ktc
N
BO N
E
E
Bo
2c
kice
desired.
14

---

7.2 MOVE-1
MOVE-1 is an efficient, optimal algorithm for an (omniscient) adversary with budget c We begin with several small insights en route to describing MOVE-1 in full.
Perturbing the Rejection Count
If p' =p, i.c., the sample statistics are left unperturbed, we obtain a false detection proportion of FDP(BHg;p] The If is possible to improve on this, can he easily shown that the case of
c= 1 we must induce an altered rejection count
K = max i [0, KPt B
henceforth referred to as the (adversarially) adjusted rejection count resulting from the adversary's choice of p'. As it turns out, for the special case of c= 1, k k is necessary if larger FDP is to be obtained, as the following lemma indicates.
Lemma 7.1. !f l/p p'llo s 1 and FDP [BH FDP[BH;;P) pl, then K + k.
Proof. We suppose the contrary for the sake of contradiction, i.e., V/ k. It follows that
[jeN:Osp)
4 N V k e
N H|
and then by [DH FDP B H pp] it follows that
Kj Ho 0 p\ < 9 | Ki Ho 0 < k H
N
Since 1p-pp Ip'o $ 1, these two conclusions are at odds, presenting a contradiction.
Considering Lemma 7.1 the adversary's p e [0, 1] decision simplifies to deciding on an adjusted rejection count k'' from among constrained set of integers consistent with the constraint -plo s 1. An optimal K can indeed be larger smaller than, even equal to k. Hence, towards understanding this new search space, it suffices to characterize the set of feasible ie' that are larger than k, and smaller.
Increasing the Rejection Count (c 1)
Towards understanding how increase the rejection count, we first highlight the following fact that follows immediately from (2).
Lemma 7.2. ifi (Te I,...,N), then BY s si- 1. In particular, BN 1:k+1
= 1.
Proof. Suppose there exists e (k + I,...,NY N} such that B. > 1-1. If BY i, then presents contradiction of (2). However, proceeding with By 2 2it + we see that there necessarily exists (i NV..,NNN for which BY = j. for this were not the case, then B j for all j E {i+1, I). meaning B.N 2 + 1, yet another contradiction since there are only N p-values.
Consequently, for i/' > i, we require a perturbed collection p' for which bin counts increase. This necessitates decrease of a p-value see Lemmal 7.5 for details. Hence, define
= (ie [Te
N): +,...,,
BY i
(8)
and note that these are precisely the positions i for which the addition of one (and only one) p-value into B1:; through the decrease of p-vauue brings i into candidacy for the new rejection count equation (2).
Proposition 7.3. - (K' kk k. 11pp p/1 s 11}
15

---

Proof. To prove the first statement, we recall that by Lemma 7.2 if > k then B < So. if i k with BY < <i- 1, then no decrease of a single p-value could increase B to i (Lemma 7.5 precluding the possibility of V = i. In other words, no L is achievable for the new rejection count K.
On the other hand, say we enumerate L with
iz > i
11 = 1:
For the case of iz, k' it is achieved if and only if p-value is decreased from any bin Bj with j > ig to bin By-s where iz 2 j-s 2 1. For the case of i,, k' is achieved if and only if p-value decreased from any bin B, with ie+1 2 j > ig to a bin Bj-s where ig 2 - s 1. Finally, all these movements of p-value just described are always possible for any given p {pilieN.
Decreasing the Rejection Count (c= 1)
Analogously, it follows that the increase of p-value is necessary for the decrease of the rejection count see Lemma 7.6 and we define
R = {ie {ir ......, k 1} BY = =iju
(9)
where i" := 0 max i (L,.... k- 1}: BY it 1). We note that R. is precisely the set of all the achievable new (decreased) rejection counts K²' i we could induce with the perturbation single p-value.
Proposition 7.4. R (K< k> RV, 1|- p' 1
Proof. We begin by proving the first statement that R/' < k implies K R. To do so, we proceed in two steps. First we show that i 2 i², so that 1" s k/' s k- 1. Then we show that if k = for some iE (1" + +, 1,...,, k- 1) in which B i, we arrive at contradiction.
To see that k' 2 i", if k,, then BY =- + becomes BY i by Lemma 7.2 in other words, the change in magnitude of B is at least 2, which contradicts Lemma 7.6 Next, if E {i" + +,...., 1). then BY i by the definition of i². This means if BA i, then BY < i, so that Lemma indiiaccss K could not be i. As for the second statement, let R be enumerated
in > in- ... 1""
For the case of iR. K' in is achieved if and only if a p-value is moved from bin B, with k j in to bin Bits > k. For R 121 r 2 2, by Lemma 7.6 it holds that K'' = i, is achieved and only if a p-value is moved from a bin By with iy+1 2 >>>> i, to bin By+. with j+ > k. Finally, for the case of i,, = = i* is achieved if and only if a p-value is moved from B3 with i" j to Bjts with j j+s k. Finally, all these movements of p-values just described are always possible for any given p= {p.hee
follows that K' he if and only if K R. so an efficient, optimal search procedure be- comes straightforward. Informally, we iterate over the bins in reverse order, beginning with N 1 and terminating with i". At iteration (/bin number) if i E L u R. then the trivial subproblem mlaxx Re (DPPBH, is solved; otherwise, nothing is done. Upon termination, the best FDP encountered is the answer. This is summarized in Theorem 7.7
Lemma 7.5 (Decreasing a p-value). Let yf be such that ||p - p/llo 1. Ifpp is the decrease of a single p-value in p from B, to Bi-so where j E (2....,Na 1) and 1 $ 8 S 1, then
i (l,..... 1-1}
B. remains constant
. .ie (j s....., j- -11
BN increases by 1
16

---

i NN....,,+I1. = B remains constant.
Lemma 7.6 (Increasing p-value)., Let p' be such that llp - p/ Ilo S 1. pf is the increase of a single
p-value in p from Bj to Bits, where [])...NN and 1 S N 1-11-. then
ie (1, ... 1} B remains constant
iE (J..... - = By decreases by
ii (j..,....., N By remains constant.
Theorem 7.7 (MOVE-I), Let E (0, 1), p-values {piliaN and sets Ho. Hi be given. For each iE LUR, let
:D max
FDP[BHH:p']
Then
max PMPosl
=
max FDP; (ECURU(()
This result explains that with one pass of the p-values from the largest to the smallest in the collection, we can ascertain the optimal perturbation p'. As the execution based on this result is straightforward, we omit the pseudocode for the sake brevity.
we compare the average performance of INCREASE-1 against that of the optimal MOVE- over 10* simulations. The experiments followed the setup described in Remark 4.6 in which N = 10s p-values are derived from independently generated z-scores, with No(= 900) null 7-scores i.i.d. N(0, 1) and (= 100) alternative z-scores i.i.d. N(11, 1), for μl 1,2. As Table indicates, INCREASE-1 can provide nearly identical performance in adjustment to FDR; however, perturbation distance z'1l is on the average much greater than MOVE-1.
In Table 3
IOVE-ICNE
E, BH,
Average 2 2
P1 2
0.140 (0.139)
0.139 (1.563)
[A1
0.775 (0.751)
0.492 (2.297)
[41
0
.992 (0.990)
0.551 (2.41)
Table 3: Sample Average batch) estimates of EEFDP[BH,; 2'1 under MOVE-1 and
INCREASE-1 1 (in parentheses) when μr 0, 1,2 and N = ==103, 0.10, mo 0.90, and all of 1.
17

---

7.3 Theoretical Analysis: Performance Guarantees and Insights into Adversarial Robustness
Theorem 4.1. cf 1, then
Do P (B). =Ni) 1b
1 2 1 P PB Ni)
c+ N1 + BINNitc
and
(N1 +c) P (B)c = Ni)
E [ [ N+1 2c]2
(6)
B
B I:N S No
Proof.
When Bi. N1, it easily follows that hise c+ Ni B No This combined with Theorem easily yields the first inequality.
As for the second inequality, let
0 == max(i E [0,N]z Big -i- - (N++c)
c)} c
Then
B 1:ke
BiN N
(N1 +
E
B%
20 c
||
B 2 c
= E
B 20 = 1- (Nr + +c +c)E E
B
20
1,0
7.0
implies that
1
B
B 2
1-E E
BR 20
E khe
B% c
60
N1 +
so that
N1 +
E [ || Blas 2 c, Ble Ni]= = E [he
B 2
1- E
BP
N. N
B N+1
2
since whenever BIc Nr. it follows that k,o koc Consequently, we derive
N1+c c
$ IE [iee B% 2 c, Bie Ni
1 E
BO N c
E Kinc Bi N,, B N+1 c]
P P(B =N1) (B N+1 2 c)
E Koei B 2 c] - E k Bic < N1. Bah 2 c]
P P(BL = N1) IP N+1 2c)
P P(B Ni) P P(BLe N1)
= E Kioc
B 2
E [kre
BiG N1, By, 2 c)
P (B = Ni)
yielding
Ni +
P P(BL. N1).
+I [htc B <N1, By. 2 Pc <N1) E ||
B 2 c].
B N
B 20
Corollary 4.2. Let n 2 1, e [0, and x a non-negative integer such that 0 S S n. If
B (Bi..., Ba) M Multinomial x. (p.....))) then TP i (n/ [Ei= B, < r])
Proof. We will appeal to the following result of 31
18

---

Lemma 7.8 (Theorem 1 of BT). Let there be
2 1 non-negative integers : 2n summing to
ग denotes a permutation drawn uniformly at random, then
Σ #R(O <r 11--11-3
Ps 0
Let it be random permutation on [I. that is drawn uniformly at random, independently
of B. Since B (Bi...., B,) ~ Multinomial (z, (p.....p)) then B₃ = (Bx(U)..... BB(n)) is
equivalent in distribution to B, or B3 2 B. Therefore,
I
|]
Pg
B
7 r=1
Σ
Bi <
E
P=
0 1
Σ i=1
Ba(D) <
x
F
Corollary 4.3, IfP: UO, 1) for all i H1.
then I (k=() = f) 1-90 (i-
1-g
IP (B for = 0, O,..., N, where 0 1,
and IP (BM, = =() =?)) (N)
(1 (1- DNN-
B c, then I' (krc = =) =(1 (1- N (1 N. ( )o-oBB (1 (1-
Bo-B N-c
Nig
N-cq
Proof. The event [k {] is equivalent to (nf-e-1 [BW. tion of two events. Regarding the event [BM f]. because Ya = O, it clear that IPBB)
Etl:s <j- [B f]. intersec-
of (1- ) To complete the characterization of P (f- () it suffices to find P ( 3-e+1 [ <j |I [BY = E)). Towards doing so, we note that conditioned on [B fJ. we have
(N-0)
(N- BW BE ~ Binom N-C, E, ② N
and, upon further conditioning on B
(BW (B8-1--.. BB Multinom BBIEN: (x) - 1-))
Hence, we derive
B. (.
P (fetet1 Biiy <j [B EJ, B.V
-
by Corollary 4.2 To conclude, integrate B. B from this derivation; more precisely,
P (nize+1 [Be-1 <j f] [BW = =])
Epy
IP (nf BBY <j <j {] || [BM, = (], BNIN) II [BW = {]]
E BN BAEN
|| [B =]]
(N-1)a
1 1-9
N-
1 q
(N-f)a
1 1-q+
(N-F)a
N
N
As for the second statement, in similar fashion to above, Corollary 4.2 yields
No - B + B
P Pa [B <j- c] || [BY. = 0], Bh BoHIN)=
N-c
implying
IP cc c] [BY. 0], BB = No B%, E B1 I:N B 0]
-
19

---

Hence,
P (kic= =c || Bx++)) =P (B =0 B8 PP j ( ctty <j- 1j-1]]
BY 0, B
=11- 44 ) (1- -NNO-Bii [1 N N
No BN-1 Niq
N C N
Theorem 4.5. Suppose Assumption 4.4 Then
A Le(g, N, No, No, == (1- eq
δ1zc M " )
No. (1- 11-me-Vo -Voc--V..o V..M Ze
N
where No N, No, PI.
No+ B Banx GunxxBBB [
E
B
B
B =0] N₁
(N-c) N-cg-Noos
N-c
Velg, N, No, P!) := V
in2 E
B B
B ltc
= -0] -0] DK
No) = N-4q E
(1 n
B&.11
Nx c-
N-c
Nc(9.N,No) = P (B 20) (1 (
No- [2
T:.
n 1 20
N-c
DKI(P*, Σ, N=c gt pr (i/N-11(
(N/cc)
Proof. Observe that A. = E
c
Ba N 2 c P (h+c= B, 1+ 20).
kic
By Theorem 4.3
IP (K.. = e, B 20) = 20)
E kro = e 1)=1); B 2
E
P (BL. =
B B) (nf [B <j-c] [B B) ) B 20
Bx
(#)
where we now proceed lower bound (#). The following discussion outlines how we proceed in the case of e= 1, but this is without loss of generality.
Let 8 and N be given, along with the event [BV 0]. Then there are No- B many null p-values and B2N many alternative p-values each of whose assignment 2,..., N remains stochastic. Let there be an arbitrary enumeration these null p-values, upon which we let the collection of their bin-assignment random variables be denoted
of bin number
B No- Let there also be arbitrary enumeration of these alternative p-values, upon which we let the collection of their PaN, ain-assignment random variables be denoted ( More precisely, af ~ ([,
N5 and af = j with probability (+ō-(a/N+61)> for j = 2,..., Finally, we will write phinn for the joint distribution derived from the independent coupling of all the random variables (a.) (a_)No- No and (at) ) For contrast, let à ((2,(( N)). which expresses the random bin assignment of any alternative p-value to one of , By given that B O, were PP1 = U 1). Then Phine, the joint derived from the independent coupling of (a.), No-B%.. and (ā²) (a)) B2x counterpoint to phins, By the chain rule for KL-ddivegeenc, we find
offers a useful
No BKc..
B Σ DKL (āllla))
DKL (phinsppping =
Σ
DKL (aflla?)
1
B2N Σ
log
N-1 qf N q- (900(9/N+)))
N
=:'K)(()11)
20

---

and by Pinsker's Inequality, for any event E,
In2 DEL (PomeljPhie
Pline Po bins (E) -V
Let df (respectively at) denote the realization of the i-th null (respectively alternative) p-value's bin Baw that
No- B8-1 and (a) (=1
assignment. Then if set E' to be the collection of realizations (a.) ( (=1 consistent with n- B2j < -1], we find
IP
(m 12 B < <j- 1]
N
BY O, BN-1 B2N)
In2
PPa, p1 (E) 2 (O(E)
DKL (Pbing [plins)
1 No B + B2N
In2
22N Dxz(PI,1)
(Corollary 422
N
2
Hence, for the case of general
(#) E
[P (n [BA c+1.
<j <j-c]
[B 0], B
N+ B Betl:N)
[B 0], B
No BN+ + B B
In2
2 EF
B1
DKL(PI,
[B = 0], B&
N-c
2
1:N
(Pinsker's Inequality)
No B
IE B Co- =]]
In2 L
21
B1
B. = 0] (PL(P),c).
--c
2
follows that
P (k_o c, 22)2
No B
B = =0]
In2
E
P (BN || Blrt))
1
E
[
c+ [B 0] DKI(P1,
: 20
N-c
2
(11 78 ( $ No- No-MBe1
To conclude,
P (hree
c, B 1)
(1
09
51c)) N1
N
No B N+1 + EE [1
BotE |l =
In2
2
E
(1
No-B
[BNlIBB 0] DKL
1 20
N
N-c
2
= =(1
c)
No
1
No + F. [[]
BotiN BBI =1
In2
E
B
BI =0] DK c)
E (1
BB+ B%
N
N-c
2
=(c,H1)
V(o.1))
(**)
B N-1
+ E
(1
c
No-
x
10
2
N
N
(een)
where
(**)
= 11-
B
B S cc-1
N - -F
eg
(1
BBy+ sc
N
N
N
(***) 2 P (B 2 (1- c
No
BB0 2c]
BB% 188 2 c
(Jensen's)
N c
21

---

Simuriation INC. REASF -5 on Marginal Conformal P-vakes
Ru-000 N,-1Bt, e 8.19, 2-15, Struladoos =1s3
Fiezuency
C
1.5
2
2.5
.559
.096
.096
.098
044
5
1
.368
.142
.135
.133
10
.997
.435
.190
.174
.170
50
.992
.657
.49
.389
.383
90
Figure 10 simulations of FDP by BHg
Table Sample Average (109-batch) estimates of IEFDP[BH,ipea on marginal conformal p- values for outlier detection (5), terms of signal strength a and budget
with and without application of INCREASE-5 on marginal conformal p-values (5] derived from an SVM one-class classifier on a test set with out-
liers drawn with a 1.5.
7.4
Simulations and Data Experiments
7.4.1 INCREASE~c Simulations on PRDS p-values
In Table 4 we illustrate the effectiveness of INCREASE-c in disrupting the nonparametric outlier detection method of (5) that based the application of BH conformal p-values, and in doing so, demonstrate effectiveness of INCREASE-C on PRDS p-values. We follow the simulation setting of Section 5.2 in [5], using their publicly available source code generate the conformal p-values. In short, a data set is generated in IR along with 10x training observations used to fit one-class SVM classifier, as well as 10th observations forming calibration set be used with test
derive (marginal) conformal p-values. In each of 10s independent replications, INCREASE-c was applied to new test set consisting of 10 conformal p-values, designed discern inliers (sigmals drawn from mixture of multivariate gaussians with identity covariance matrices) from outliers (signals drawn from a mixture of multivariate gaussians with identity covariance matrices scaled by a strength va). This was performed for a {1,1.5, 1.5, 2, 2.5,3) 3): signal strength a corresponds to identical null and alternative distributions, while larger values of make it easier detect outliers. We set the fraction of outliers in each test set to = .1. so that fraction To .90 of the observations are inliers each data set.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction preciscly summarize the results of our paper's
content.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we discuss to what extent our analysis could be extended and further generalized, but were done due to space constraints.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our appendix contains the full proofs of all theoretical results.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All such information is disclosed in Experimental Results section.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Experiments conducted were either with simulations on synthetic data, or Kaggle data set in which the URL is provided. They are simple to set up, and we described them precisely. The codes we implemented were either our own scripts, or code that we cited from 5
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Training of isolation forest was done in Section 5.2 Training of one-class SVM was also done in Appendix Section 7.44 executed with their publicly available code http://gthhb.commsssiiccottttttt
77.4when when we implemented the simulations S
conformal-pvalues.se
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We found it unnecessary to report error bars as the purpose behind our simulations was to showcase/illustatte how large the false detection proportion could be made as result small perturbation. Further, the simulation averages were consistent with our theory.
23

---

8. Experiments Compute Resourees
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: See Section 5
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We affirm that the research conforms to the code of ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the Introduction and Conclusion we discuss potential concerns for safety- security settings
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer:[NA]
Justification: [NA]
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We give credit to 5 for the code we implemented in our own experiments.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
24


Reviews:
[{"review_id": "dyZkhrSaig", "reviewer": "Reviewer_pEvv", "summary": "The paper explores the adversarial robustness of the Benjamini-Hochberg procedure. In particular, the authors theoretically show that it is possible to perturb test scores to cause the BH procedure to not be robust to adversarial attacks. BH is reframed as a \"balls into bins\" problem, and the authors propose an algorithm (INCREASE-c) to increase the rejection count. The authors also provide experiments to support their theoretical findings.", "questions": "- Problem setup questions:\n\t- What is the rationale for the attacker having access to z-scores at that stage of the pipeline? Usual studies consider attackers having access to data, and it may take quite a lot of changes in data points to change a z-score.\n\t- Why is the attacker's knowledge of $q$ realistic? I assume that in some models, the deployment will come with a (public) guarantee for $q$ -- but this should be at least mentioned.\n\t- It would be good to have a comment justifying the choice of perturbation ( $||\\cdot||_0$ ), which I suppose is because BH is an algorithm for order statistics. What happens when considering a different type of budget (e.g., arbitrary $||\\cdot||_p$ norms)?\n- l.128-132: When are these assumptions met in practice?\n- What is the impact of attacking BH procedure on the whole OOD system? Can you break OOD detection in a meaningful way?\n\n\n****\n\nPost-rebuttal: I have increased my confidence score from 2 to 3 following the authors' response and other reviews.", "limitations": "I think some of the problem setup questions above would address some limitations of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The technical contribution seems solid and sound.\n- There is a clear novelty aspect, as the adversarial robustness of BH has not been considered before.\n- The authors show an interesting gap between distributional robustness (which was shown to hold (ref [29] in the paper)) and adversarial robustness for BH procedure.\n- The (synthetic) statistical experiment supports the theoretical claims.", "weaknesses": "- In the introduction, the paper (correctly) highlights the importance of hypothesis testing to various safety applications such as OOD detection. However, the experimental section does not, in any capacity, consider an end-to-end application such as OOD detection. In fact, it reads purely as a statistical simulation (which is fine as a synthetic experiment). But a minimal experiment with a MNIST/FashionMNIST OOD-classifier, to show that indeed the Z-scores can be affected by INCREASE-c could make the paper much stronger.\n- The attack is dependent on the algorithm (BH) used for FDR -- stronger results in adversarial robustness are often model/algorithm-independent.\n- There seems to be a certain lack of justification for choices in the problem setup (addressed in questions below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Addressing Weaknesses**\n\n1. *In the introduction, the paper (correctly) highlights the importance of hypothesis testing $\\ldots$ However, the experimental section does not $\\ldots$ consider an application such as OOD detection \\ldots*\n\n**Rebuttal:**\nWe did in fact experiment on an ``OOD-classifier.\" We refer you to our Section 5.2's experiments on the non-parametric outlier detection method proposed in the paper by Bates, Candes, et al 2023 based on conformal p-values. Specifically, we repeated the experiment in their paper that produced conformal p-values with a trained, SVM one-class classifier, only now we added small corruption to see how badly their OOD system might mistake inliers for outliers. \n \n2. *The attack is dependent on the algorithm (BH) used for FDR -- stronger results in adversarial robustness are often model/algorithm-independent.*\n\n**Rebuttal:**\nBH is the tool of choice for large scale hypothesis testing, with over 100K Google scholar citations of the original paper. BH is also emerging in AI/ML for out-of-distribution-detection (OOD) - for example, see Lieu et al 2024 (accepted at the recent ICML 2024) and Bates, Candes et al 2023. In other words, BH would seem to be a natural and relevant choice for an adversarial study. \n\nFurther, BH belongs to the family of step-up procedures, which means the rejection region is decided via a stopping time (see our analysis), which since our paper shows can be manipulated, it means other ``step-up\" procedures\" are similarly prone.\n\n**Addressing Questions**\n\nQuestion 1. *What is the rationale for the attacker having access to z-scores at that stage of the pipeline? Usual studies consider attackers having access to data, and it may take quite a lot of changes in data points to change a z-score.*\n\n**Rebuttal:**\n\nThank you for your comment. For what it's worth, changes in the data translate into changes at the z-score level. As for the size of changes, in Page 16, Appendix Table 3, the algorithm MOVE-1 on average moved the z-score .551, .492, and .139 in the settings of $\\mu_1 = 0, 1,$ and $2$ respectively. Granted, the effect of data-point perturbations on z-scores would ultimately also be affected by matters like sample size and standard deviation. That being said, we are more focused on applications in outlier detection or out-of-distribution-detection (OOD), as in Bates et al 2023, which we referenced several times and use as an experimental baseline in Section 5. \n\nMore precisely, in this context, they consider a statistical wrapper that, broadly speaking, transforms each $X_i$ in a collection\n$X_1, X_2, \\ldots X_n$\nof signals (measurements) into a p-value $p_i \\in [0,1]$, the total collection $(p_j)_{j=1}^n$ of which then corresponds to $n$ hypothesis tests to be conducted simultaneously, each of which determines whether a signal $X_i$ is an anomaly/outlier. Therefore, perturbations in this context affect the $X_i$ scores directly. \n\nFor further discussion on this, we kindly refer you to our answer to reviewer L7r5's question \\#1.\n\nQuestion 2. *Why is the attacker's knowledge of $q$ realistic? $\\ldots$*\n\n**Rebuttal:**\n\nIndeed, your point about a \"public guarantee\" that would grant the adversary knowledge is realistic, with values of $q = 0.05, 0.10$ a standard practice.\n\nOn a related note, while it is possible for the adversary to not precisely know the true control level $q$ to be implemented by the decision maker, this opens the door to some really interesting attacker-defender dynamics between the adversary and decision maker that we are in fact studying in a follow-up work. In any case, we confirm that there are measures that can be taken by the adversary towards harming FDR control even without perfect knowledge of $q.$\n\nQuestion 3. It would be good to have a comment justifying the choice of perturbation $(||\\cdot||_0)$, \n\nwhich I suppose is because BH is an algorithm for order statistics. What happens when considering a different type of budget (e.g., arbitrary $||\\cdot ||_{p}$ norms)?\n\n**Rebuttal:**\n\nViewed from the perspective of outlier detection, our study is considering an adversary attempting to make the decision maker confuse inlier signals for outlier signals or vice versa. For some particular motivating applications, consider candidate screening, spotting frauds/intrusions, and forensic analysis - applications discussed in Bates, Candes, et. al 2023 and Jin, Candes 2023. In such contexts, we think it is natural that the *number* of hypothesis tests (equiv. signals) that an adversary can influence is bounded - hence, the modeling choice of a budgeted $\\|\\cdot \\|_0$. This choice was sufficient to demonstrate a fragility to BH's FDR control. More precisely, the attacker can break the BH guarantee by moving few z-scores. But, yes, other measures ($\\|\\cdot \\|_p$ norms) of corruption effort might be considered as well. \n\nQuestion 4. *l.128-132: When are these assumptions met in practice?*\n\n**Rebuttal:**\n\nThe lines l.128-132 do not detail assumptions; rather, all we mean to say in these lines is that the corruption model we propose is most interesting in scenarios where not too many tests get rejected, for otherwise any attack would have to be massive in order to have an effect on the FDR. Indeed, the number of rejections $R_p$ comprises the denominator in the false detection proportion $FDP[\\mathcal{A};p]:= \\frac{a_p}{R_p \\vee 1}$. Regardless, the theoretical results hold true under any values of $N$, $q$, and the collection of $\\mu_1^i$'s.\n\nQuestion 5. *What is the impact of attacking BH procedure on the whole OOD system?... break OOD detection?*\n\n**Rebuttal:**\n\nFigure 4 and Table 2 detail the experiments we conducted on the OOD \"system\" that Bates, Candes, et al 2023 studied. In particular, in Table 2, the average proportion of the reported outliers that are in fact inliers is reported. As one can see, there can be significant impact on OOD systems based on BH (of which there are several recent publications on).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cjqZNTn8us", "reviewer": "Reviewer_L7r5", "summary": "In this paper, the authors have tested the Benjamini-Hochberg (BH) 's adversarial robustness, as this procedure is deployed in critical applications such as drug discovery, forensics, and anomaly detection. Specifically, the authors develop a class of simple and easily implementable adversarial test-perturbation algorithms to analyze under what conditions BH does and does not exhibit adversarial robustness. Next, to support their findings, the authors provide non-asymptotic guarantees on the expected adjustments to the FDR due to these adversarial attacks. Their technical analysis involves a combinatorial reframing of the BH procedure as a \"balls into bins\" process. It connects this to generalized ballot problems to utilize information-theoretic approaches for deriving non-asymptotic lower bounds. Finally, the authors also conducted experiments to support their findings.", "questions": "- In practical scenarios, an adversary manipulates the input directly, not the z-scores; thus, could the authors provide more insight into how perturbations applied to z-scores translate back to the original data samples or vice-versa? Or, when the inputs are perturbed, what will impact the proposed analysis of the BH algorithm (given the z-scores computed from the input samples)?\n\n- A statement on Page 4: \"A benefit of this approach is that perturbation at the level of z-scores places the corruption more directly at the point of data collection than does perturbation of the p-values.\" Could the authors answer: Won't the perturbation at the data collection directly place the corruption at the data level? Also, why was it not assumed to be corruption at the data level, then the computation of either the z-scores or the p-values? How this mapping between the data and the z-scores is computed?\n\n- The evaluation results are a bit difficult to navigate in the paper. For example, Figure 1 and Figure 4 are not understandable. Could the authors make the evaluation section comprehensible?\n\n- Could the authors add more evaluations to test how the proposed method performs with real-world data?\n\n\nPost-rebuttal: I have changed my rating from borderline reject to borderline accept, confidence from 3 to 4, and soundness of the paper from 2 to 3.", "limitations": "Same as Weaknesses.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- In this paper, the authors provided a detailed theoretical analysis of the BH procedure's robustness against adversarial attacks. They also introduced the INCREASE-c algorithm, which gives methodical mathematical bounds and probabilities for different cases (large and small alternative means).\n\n- I liked how advanced probabilistic and statistical tools, such as KL divergence and Pinsker's inequality, are used to provide a solid mathematical foundation for the analysis. The proofs and the lemmas were thoroughly justified.\n\n- Finally, the paper presentation is well-structured. The paper's organization is clear and logical. In each section, a comprehensive analysis is done and well-presented.", "weaknesses": "- In practical scenarios, an adversary manipulates the input directly, not the z-scores; thus, the insight into how perturbations applied to z-scores translate back to the original data samples or vice-versa is missing in the paper. \n\n- My other concern is that since z-scores are computed only utilizing the means and the standard deviation of the sample, the manipulation at the data level can get lost at the z-scores level.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Q1 Re:\n Indeed, $z$ scores are classically $z_i := \\frac{\\sum_{j=1}^n x_{ij}/n - 0}{s/\\sqrt{n}}$, so that perturbations to the \"samples\" $x_{ij}$ translate to perturbation of the z-score $z_i$, and ultimately the p-value $p_i:= 1 - \\Phi(z_i)$. Since p-values are ultimately the input processed by BH, our model is not concerned with how perturbations of the input samples $x_{ij}$ are made, so long as the $p_i$ value is affected. \n\nFor a broader perspective on this matter of samples versus z-scores versus p-values, we call to mind the application of ``conformal p-values\" by Bates, Candes, et al 2023 that strongly motivated this work, and for which we reference several times, and implement their experiments within ours in Section 5.2. In particular, they consider a statistical wrapper that transforms each $X_i$ in a collection $(X_j)_{j=1}^n$ \n\nof signals (/measurements) into a p-value $p_i \\in [0,1]$, the total collection $\\{p_j\\}_{j=1}^n$ of which corresponds to $n$ hypothesis tests to be conducted simultaneously, each of which determines whether a signal $X_i$ is an anomaly, or outlier. Therefore, in this context, perturbations to a score $X_i$ is direct. \n\n# Q2 Re:\n\nAs far as theoretical analysis, our work is largely free of distributional assumptions, so there is little \"impact\" from \"data-generating distribution changes.\" For instance, it is w.l.og. that the null p-values are Uniformly distributed. As for the alternative distributions, we made few assumptions throughout. Indeed, Theorems 3.1, 3.2 after all do not make any distributional assumptions on the alternatives. The bound provided in Theorem 4.4 is a function of the $\\mu_1^i$, which as we discussed in Section 4.2, can also be replaced with max $\\mu_1:= \\max_{i \\in \\mathcal{H}_1} \\mu_1^i$ for a more conservative bound. \n\nAs far as numerical analysis, it was for the sake of experiments that we made assumptions on the alternative distribution, as do all papers dealing with the BH procedure - see Bates, et al 2023 for example.\n\n# Q3 Re:\n To the best of our understanding, we address your concern in our answer to Question 1, so we kindly refer you to the answer we provided above.\n\n# Q4 Re:\n With regards to the Type II error, since all the z-scores will be in the rejection region, there would be no failure in rejecting any $i \\in \\mathcal{H}_1$ (i.e. any test for which the ``alternate hypothesis is true\"); hence, there would be no Type II error, by definition. For what it's worth, although Type II error is of note, false discovery rate control is concerned with Type I error. \n\n# Q5 Re: \nIf we're not mistaken, in the \"same case above\", the alternative distributions' being \"close\" to the null is a non-factor. Indeed, you provide an event in which all $N$ z-scores are rejected, so the Type II error is 0, as above. As for the FDP in this event, it would be forced to be $\\pi_0$ because this is the fraction of scores out of $N$ that are null. \n\nIf you are asking about FDR control in the case of alternative distributions being \"close\" to the null distribution, this is precisely the subject of Section 4.2, wherein we provide a theoretical lower bound (Theorem 4) on how much the adversary can increase the FDR with INCREASE-c. This bound is plotted in Figures 2 and 3 of Section 5, in which we examine, respectively, the extreme case when the alternative distributions are identical to the null distribution and a case where they are not identical but roughly speaking, about a quarter standard deviation away from each other. The point to these plots is to illustrate the fragility of the BH FDR control when the alternative and null distributions are \"close\".  \n\n# Q6 Re:\n The frequency color of a plotted dot at $(FDP[BH_q; p]$, $FDP[BH_q; p_{+c}]) \\in \\mathbb{R}^2$ indicates how many of the $10^4$ simulations produced that combination of before-adversary and after-adversary FDP. Figures 1 and 4 illustrate how very frequently the adversary's INCREASE-c not only increased the FDP (above the $45 \\deg$ line) but also raised it above the theoretical control level of $\\pi_0 \\cdot q$ (above the horizontal line). This high frequency illustrates a breaking of BH's FDR control. \n\n# Q7 Re:\n We believe you are referring to Section 5.1, line 311 which states $z_{i \\in \\mathcal{N}_0} \\sim N(\\mu_1, 1)$. \n\nThere was a typo in the subscript, and should actually read: $z_{i \\in \\mathcal{N}_1} \\sim N(\\mu_1, 1)$. \n\n# Q8 Re:\n We followed the approach taken in most BH-procedure papers, where the experiments are over a range of $\\mu_1$. Unfortunately, not all parameter choices could be explored/presented within a 9-page paper. For what it's worth, follow-up experiments do not seem to indicate anything that we haven't showcased already. \n\n# Q9 Re:\n  We executed the algorithm just as described on page 5. We \"move the largest $c$ (ties broken arbitrarily) in the (N+1)-th bin to bin $\\tilde{k}_{+c}$.\" More precisely, as our z-scores were stored in memory with vectors, ties were broken by taking whichever z-score occurred earlier in the vector's indexed-ordering. \n\n# Q10 Re:\n Section 5.3's experimental setup involved repeated simulations of $N = 10^3$ p-values drawn just as described in Section 5.1. Regarding the experiment that produced Figure 2, as the caption indicates, we had parameter settings of $\\mu_1 = 0$, $\\pi_0 = .90,$ and $c = 1.$ As for $q$, as the figure indicates, this was now varied across a grid of $q \\in (0,1)$ (mesh spacing of .01). For each $q,$ we performed the repeated simulations, in each of which we computed $FDP[BH_q; z_{+c}] - FDP[BH_q; z]$, so that averaged across all simulations we obtained $\\Delta_1(q)$. Repeated for all $q \\in (0,1)$, we obtained the blue curve that is labeled $\\Delta_1$. The red curve is $L_c$ from Theorem 4.4 as a function of $q$. Regarding the experiment that produced Figure 3, as the caption indicates, we had parameter settings of $\\mu_1 = 0.25$, $\\pi_0 = .95,$ and $c = 1.$ The rest of the details are just as described above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YWjDH11XtC", "reviewer": "Reviewer_3drS", "summary": "This paper studies the adversarial robustness of the Benjamini-Hochberg (BH) procedure, introducing simple adversarial test-perturbation algorithms. The experiments show that BH's control can be significantly compromised with minimal perturbations. The analysis uses a combinatorial perspective and generalized ballot problems to derive non-asymptotic lower bounds.", "questions": "Please refer to the weaknesses.", "limitations": "The authors' justification is \"Yes, we discuss to what extent our analysis could be extended and further generalized, but were not done due to space constraints.\". However, even in Appendix, there is not any analysis of limitations.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper addresses a novel and significant aspect of the BH procedure—its adversarial robustness. This research probelm is relatively unexplored, providing new insights into the vulnerabilities of widely used statistical methods.", "weaknesses": "This paper would benefit from a discussion of potential mitigation strategies that could enhance the robustness of the Benjamini Hochberg procedure against attacks such as INCREASE-c.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Addressing the Weakness comment $\\ldots$\n\n*This paper would benefit from a discussion of potential mitigation strategies that could enhance the robustness of the Benjamini Hochberg procedure against attacks such as INCREASE-c.*\n\n**Rebuttal:**\n\n**Thanks for asking about mitigation strategies, which we view as an important follow-up question to this paper's thesis that BH's FDR control can be susceptible to minimal adversarial perturbation. In fact, we are in the midst of preparing this follow-up work. We kindly refer you to our answer to Reviewer pEvv's question #2, in which we briefly comment on interesting dynamics to the attacker-defender interaction, including some insights into mitigation strategies studied in this said follow-up work. Given that our submission as it stands now rides right up to the 9-page limit, with a moderate amount of appendix material already, we believe that the study of mitigation strategy extensions would be better positioned as a separate paper.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yyoaUItjp2", "reviewer": "Reviewer_niTJ", "summary": "Benjamini-Hochberg provides a means for controlling the false detection rate (FDR) in multiple hypothesis testing.  This paper explores how the FDR region can be perturbed by an adversary.  Specifically, the author(s) propose two adversarial attacks *Increase-C* and *MOVE-1* to efficiently perturb *c* scores and 1 score, respectively.  The author(s) prove analytical bounds on their attacks' guarantees.  The author(s) also provide simulated experiments demonstrating their attacks effectiveness on synthetic z-scores.", "questions": "None.", "limitations": "This paper describes two adversarial attacks and identifies the brittleness of Benjamini-Hochberg.  While such work inherently creates a non-zero risk, there are no serious negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I was not familiar with Benjamini-Hochberg before reading this paper (I did not bid on the paper).  However, with significant effort and outside reading, the paper was still attainable.  That is a strength of the work in general.  The *Balls in Bins* warm-up was definitely helpful to a reader.  I provide comments on how this warm-up could be improved below.\n\n### Novel Area and Good Execution\n\nTo the extent of my knowledge, no existing work has studied the adversarial robustness of methods to control FDR.  I discuss why I believe that is below in the limitations section.  Nonetheless, the authors provide reasonable first-pass attack methods that are intuitive and performant.  They even provide an optimal method in the case of singleton perturbations.  The authors also provide thorough theoretical analysis.", "weaknesses": "### Very Little Analysis of Section 5's Empirical Results\n\nSections 5.1 and 5.2 are essentially just an overview of the two experimental setups.  There is no real analysis or discussion of what the experimental results show or why it's important.  While Section 5.3 has some basic analysis, it is again quite minimal.  I understand that the page limit forces difficult decisions over content but so little in the way of commentary on the results is a disservice to the reader and overall a poor choice.\n\nI would have preferred empirical results on real datasets as opposed to the toy datasets in the paper, but I understand the author(s)'s choices here, especially given related work.\n\n### Move-1 Relegated to the Appendix\n\nBeyond a very definition in Section 1.5, all discussion of MOVE-1 including how the method works and why its optimal are relegated to the appendix.  There should at least a basic overview of the key ideas of MOVE-1 including some basic intuitions how it differs from INCREASE-c in the main paper. \n\n### Making the Work More Intuitive\n\nSection 2 in my view is a warmup for readers to help build intuitions and understanding of BH, even if they are not familiar with the related background. Section 2 could be significantly improved if figures were used to better illustrate the key ideas.  These figures need not be large and any additional camera ready page could be used to visualize the ideas.  Even if the authors chose not to include such figures in the main paper, they could be in the appendix.\n\n### Limited Potential Impact\n\nThere is undeniable merit and utility in studying the robustness of a method that provide tools to control FDR, such as Benjamini-Hochberg.  Nonetheless, this work falls essentially is a niche (BH) within a niche (adversarial analysis).  Hence, I view it as unlikely that this work will have a significant impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Addressing the *``Weaknesses\"* $\\ldots$\n\n*1. Very Little Analysis of Section 5's Empirical Results*\n\n   *Sections 5.1 and 5.2 are essentially just an overview of the two experimental setups. There is no real analysis or discussion of what the experimental results show or why it's important. While Section 5.3 has some basic analysis, it is again quite minimal. I understand that the page limit forces difficult decisions over content but so little in the way of commentary on the results is a disservice to the reader and overall a poor choice.*\n\n   **Rebuttal:**\n\n   **In terms of Sections 5.1 and 5.2, which concern simulating INCREASE-c on iid and PRDS p-values respectively, we had thought the figures and tables illustrated the effectiveness of INCREASE-c far better than words could. Indeed, the page limit did severely constrain some discussions, but if given the opportunity to, we would absolutely correct this with more elaboration, as you suggest. For what it's worth, what we had intended for the reader to understand from Figure 1, was that with both colors and lines, we were indicating how frequently INCREASE-c not only increased the FDP (above the $45^\\circ$ line) but also raised it above the theoretical control level of $\\pi_0 \\cdot q$ (above the horizontal line), or in other words, broke BH's FDR control. Likewise in Table 1, the high average FDP numbers and perturbed rejection counts illustrate the effectiveness of INCREASE-c. Figure 4 and Table 2 communicated the similar conclusion but for PRDS conformal p-values.**\n\n   *I would have preferred empirical results on real datasets as opposed to the toy datasets in the paper, but I understand the author(s)'s choices here, especially given related work.*\n\n   **Rebuttal:**\n\n   **Thanks for your input. For us, given the choice between a real dataset and a simulation-procured, synthetic dataset of Bates, Candes et al 2023 -- with publicly available code which they used to conduct their experiments -- we felt our message on BH's fragility would be stronger by repurposing their code for comparison's sake. Consequently, in light of the page limit, we had to compromise on the real datasets.**\n\n*2. Move-1 Relegated to the Appendix*\n\n   *Beyond a very definition in Section 1.5, all discussion of MOVE-1 including how the method works and why its optimal are relegated to the appendix. There should at least a basic overview of the key ideas of MOVE-1 including some basic intuitions how it differs from INCREASE-c in the main paper.*\n\n   **Rebuttal:**\n\n   **We thank you for your interest and appreciation of MOVE-1. Of course we appreciate it too, but it not only pertains to the very special case of $c = 1$ but also does not strongly outperform INCREASE-1 empirically per se, despite its theoretical optimality in this case. Indeed, the INCREASE-c algorithm is arguably easier to describe and implement, and of course handles all possible $c$ value cases. Our theoretical performance analysis guarantee was also designed specifically for INCREASE-c. Hence, for all these reasons, and in light of the 9 page limit, we did not feel as though discussing MOVE-1 in detail had good bang for buck.**\n\n*3. Making the Work More Intuitive*\n\n   *Section 2 in my view is a warmup for readers to help build intuitions and understanding of BH, even if they are not familiar with the related background. Section 2 could be significantly improved if figures were used to better illustrate the key ideas. These figures need not be large and any additional camera-ready page could be used to visualize the ideas. Even if the authors chose not to include such figures in the main paper, they could be in the appendix.*\n\n   **Rebuttal:**\n\n   **Your suggestions to use illustrations to enhance the readability of the mathematical description of the Balls into Bins perspective on BH are duly noted. Thank you!**\n\n*4. Limited Potential Impact*\n\n   *There is undeniable merit and utility in studying the robustness of a method that provides tools to control FDR, such as Benjamini-Hochberg. Nonetheless, this work falls essentially is a niche (BH) within a niche (adversarial analysis). Hence, I view it as unlikely that this work will have a significant impact.*\n\n   **Rebuttal:**\n\n   **Thank you for your assessment. The BH is the tool of choice for large scale hypothesis testing, with over 100K Google scholar citations of the original Benjamini and Hochberg \"Controlling the false discovery rate: a practical and powerful approach to multiple testing\" paper. As well, in the intro to our paper, we also cite a handful of more modern works in AI/ML that are leveraging BH in some way for out-of-distribution-detection (OOD) - among them, Lieu et al 2024 (accepted at the recent ICML 2024) and Bates, Candes et al 2023. So, we believe a paper examining BH's fragility is relevant and important.**\n\n---", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their questions and feedback. We have provided individual responses to each and welcome the opportunity to engage further in the discussion period.

Meta-review: The paper investigates the conditions under which the Benjamini-Hochberg procedure is resilient to adversarial attacks.  In addition, the authors reframe the BH procedure as a "balls into bins" process as well as propose an algorithm to increase the rejection count. Finally, the authors also conducted experiments to support their findings.

All the reviewers had positive opinion on the paper, though in some cases this would come with low confidence as BH is not a well-known approach within the machine learning literature.  Nevertheless, good discussion was generated during the rebuttal period and on one hand several clarifications were provided or reviewers' questions were answered by the authors, and on the other hand the authors also agreed to add information on the final version of the paper that would make the final manuscript more accessible to everyone and on-par with other papers that are accepted in NeurIPS. Along these lines, in the final version of the paper clarifications are expected on matters like z-score, perturbation, norm choice, adversary power, etc.  Furthermore, the authors also performed experiments on a real-world dataset during the rebuttal period and these experimental results further elucidate the authors' approach as it was requested by the reviewers. I expect that these results will be included in the final version of the paper in one way or another.  For example, the authors may find it more reasonable to hint about these additional experimental results in the main text of their paper and provide full details in the supplementary material.
Decision: Accept (poster)