A Bandit Approach to Multiple Testing with False Discovery Control
We propose an adaptive sampling approach for multiple testing which aims to maximize statistical power while ensuring anytime false discovery control. We consider n distributions whose means are partitioned by whether they are below or equal to a baseline (nulls), versus above the baseline (actual positives). In addition, each distribution can be sequentially and repeatedly sampled. Inspired by the multi-armed bandit literature, we provide an algorithm that takes as few samples as possible to exceed a target true positive proportion (i.e. proportion of actual positives discovered) while giving anytime control of the false discovery proportion (nulls predicted as actual positives). Our sample complexity results match known information theoretic lower bounds and through simulations we show a substantial performance improvement over uniform sampling and an adaptive elimination style algorithm. Given the simplicity of the approach, and its sample efficiency, the method has promise for wide adoption in the biological sciences, clinical testing for drug discovery, and online A/B/n testing problems.
This paper considers adaptive allocation strategy that guarantees FWER or FDR in n distinct one-armed bandit problems (two-armed bandit problems with parameter \mu_0 known). While I think the results are interesting and the technologies used in this paper are sound (at least with some modifications), the current exposition of paper has many spaces for improvements. Mathematical notions are somewhat loosely used (detailed in major/minor remarks). The contribution of the proposed algorithm is not very easy to follow.  On the structure of the paper, (i) 1.3 Related work is rather long. In 8-page submission, a typical length of related work would be < 1 page.  (ii) 1.2 summary and 3 main results are overlapping: the first appearance of the main result should be presented with the main theorems.  Major remarks  >On Table 1  (i) To my understanding, these bounds are upper bounds. Is there any corresponding lower bounds?  (ii) What is the number of samples when uniform sampling is adopted? Are improvements of Alg 1 over uniform sampler significant? (iii) Use landau notation O(n \Delta^-2) for upper bound \Omega(n \Delta^-2) for lower bound.  >Algorithm 1 Alg 1 is not fully algorithmic because the lines begin with “Apply” are not stated algorithmically (appears to be detailed in Sec 2.1).  >On the novelty of Alg 1.  The algorithm utilizes standard multiple testing tools (BH and Bonferroni corrections) and the anytime p-value. One fear is that Alg 1 is a naive combination of these technologies. Could the authors highlight the innovative part of the Alg 1?  Minor remarks  Def 5: smallest time: Is sample complexity random variable?  Remark 1 takes me a significant amount of time to understand: I finally got the idea that no algorithm can stop with guarantee of TPR and FWPD, but I believe that the presentation can be improved. Line 97-98 hold only for one-sided test where \mu_i >= \mu_0. Line 133 p-value is undefined at this point Line 211/227 FDR(FWER)-controlled - these properties of sets are undefined. Line 262: independent of all problem parameters: universal constant? Line 265: do not use footnote right after math mode (c^3 looks like c-cubic). Line 267: Do not redefine H_1, H_0, Deltas. Line 271: Neither argument of the minimum follows from the other. > I could not understand.  #after author response The author rebuttal is helpful to me as they make some points clear (especially, the lower bounds: line 109-119).  The authors state that the sample complexity is a (high-probability-bounded) random variable, which sounds unconventional to me (for example, sample complexities H1 and H2 in "Best Arm Identification in Multi-Armed Bandits" are dist-dependent constants).   # Contribution and Presentation As stated in Appendix A, one of the novel contributions of this paper is to avoid union bound over arms to improve logarithmic factors, which I think novel. I found no critical error in the paper. I feel the paper is not very well written in representing their mathematical contents. Some formulas are redefined (e.g. H1, H0, Delta_i, Delta in Thm 1). Lemmas in Appendices are even more sloppy: For example, it takes some efforts to check whether or not P_{i,t} and S_t in pp.11-12 are the same as the ones defined in the main paper. Lemma 2 defines T_i that is used in S_t, which is not defined in the statement of Lemma 2.