  The false discovery rate (FDR) and the false non-discovery rate (FNR),
defined as the expected false discovery proportion (FDP) and the false
non-discovery proportion (FNP), are the most popular benchmarks for multiple
testing. Despite the theoretical and algorithmic advances in recent years, the
optimal tradeoff between the FDR and the FNR has been largely unknown except
for certain restricted classes of decision rules, e.g., separable rules, or for
other performance metrics, e.g., the marginal FDR and the marginal FNR (mFDR
and mFNR). In this paper, we determine the asymptotically optimal FDR-FNR
tradeoff under the two-group random mixture model when the number of hypotheses
tends to infinity. Distinct from the optimal mFDR-mFNR tradeoff, which is
achieved by separable decision rules, the optimal FDR-FNR tradeoff requires
compound rules even in the large-sample limit and for models as simple as the
Gaussian location model. This suboptimality of separable rules also holds for
other objectives, such as maximizing the expected number of true discoveries.
Finally, to address the limitation of the FDR which only controls the
expectation but not the fluctuation of the FDP, we also determine the optimal
tradeoff when the FDP is controlled with high probability and show it coincides
with that of the mFDR and the mFNR. Extensions to models with a fixed non-null
proportion are also obtained.
