Fast confidence bounds for the false discovery proportion over a path of hypotheses

Author:

• Guillermo Durand - Université Paris-Saclay, CNRS, Inria, Laboratoire de Mathématiques d'Orsay, 91405, Orsay, France

Abstract

This paper presents a new algorithm (and an additional trick) that allows to compute fastly an entire curve of post hoc bounds for the False Discovery Proportion when the underlying bound $V^_{\mathfrak{R}}$ construction is based on a reference family $\mathfrak{R}$ with a forest structure à la @MR4178188. By an entire curve, we mean the values $V^{\mathfrak{R}}(S_1),\dotsc,V^*{\mathfrak{R}}(S_m)$ computed on a path of increasing selection sets $S_1\subsetneq\dotsb\subsetneq S_m$, $|S_t|=t$. The new algorithm leverages the fact that going from $S_t$ to $S_{t+1}$ is done by adding only one hypothesis. Compared to a more naive approach, the new algorithm has a complexity in $O(|\mathcal K|m)$ instead of $O(|\mathcal K|m^2)$, where $|\mathcal K|$ is the cardinality of the family.