No significant tests when using Benjamini-Yekutieli multiple testing correction on millions of tests

I am using a univariate filter to reduce the number of features prior to applying a learning algorithm to a huge binary classification dataset (22510066 features x 500 examples). All the features are binary-valued (0 or 1). Most of these features are supposed to be irrelevant. I am using a $\chi^2$ test to obtain a p-value for each feature and then, based on some significance threshold, I would like to keep only the significant features.

Since I am performing so many hypothesis tests, it is necessary to correct for multiple testing. I have chosen to use a method that limits the FDR, as it seems more natural for feature selection. The features in the dataset are not independent and some of them are negatively correlated, thus I am using the Benjamini-Yekutieli method to do the correction. After computing the p-value for each feature, the minimum p-value is 2.7061601033755451e-09.

I have noticed something that I do not understand. If I set the maximum FDR ($\alpha$) to 1.0, which means that the proportion of type I errors is $\leq 1.0$, even the smallest p-value is not small enough to be considered significant. I understand that alpha is an upper bound on the FDR and that if $\alpha=1.0$, it does not mean that 100% of the tests for which the null hypothesis was rejected are type I errors, but I still don't know how to interpret this result.

Could someone please help me interpret this result? Does this mean that the Benjamini-Yekutieli procedure is not powerful enough for such a huge number of tests?

• Two issues: First, the paper of Benjamini and Yekuteli (2001) assumes positive regression dependency of the test statistics, not negative. Second: It would be no problem for a test to break down for $\alpha=100%$ since nobody needs this anyway. Maybe these superficial comments help. – Horst Grünbusch Apr 15 '15 at 22:01
• Hi Horst, thanks for your reply! I am using the version of Benjamini and Yekutieli that is valid under arbitrary dependencies (see here). I agree that there is no use for a method that is valid at $\alpha=100$. I am asking this question, since at such a high value for alpha, I would have expected to have at least a few significant tests. – jamesbond Apr 15 '15 at 22:12
• There are 122 significant tests at $\alpha=1.1$. – jamesbond Apr 15 '15 at 22:16
• @HorstGrünbusch The Benjamini-Yekutieli paper refers to the Benjamini-Hochberg FDR adjustment as requiring either independence or positive dependence. The Benjamini-Yekutieli procedure is applicable to dependent tests (regardless of positive or negative dependence), as the last two sentences of the abstract make abundantly clear. – Alexis Apr 15 '15 at 22:17
• jamesbond, you should be choosing FDR for values of $\alpha$ akin to what you would use for a single test (e.g. 0.05, 0.001, etc.). Also: both the B-H and the B-Y procedures are step-down procedures, meaning that the decision to reject a test depends on more than simply its adjusted p-value, but also on the ordering of its unadjusted p-value relative to other tests. – Alexis Apr 15 '15 at 22:21

• Nice answer. A quibble, though: it is inaccurate to say that the BY procedure is as conservative as the Bonferroni adjustment, as the BY amounts to using the BH with $\alpha/C$ where $C=\sum_{i=1}^{m}{i^{-1}}$, where $m$ is the number of comparisons. In @jamesbond 's case, $C=17.50669$, so the BY amounts to the BH for $\alpha/17.50669$ which is a far cry from the $\alpha/22510066$ for the Bonferroni. – Alexis Apr 15 '15 at 22:29