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

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^{\ast }\_\mathfrak{R}$ construction is based on a reference family $\mathfrak{R}$ with a forest structure {Ã } la Durand et al. (2020). By an entire curve, we mean the values $V^{\ast }\_\mathfrak{R}(S\_1),\dots ,V^{\ast }\_\mathfrak{R}(S\_m)$ computed on a path of increasing selection sets $S\_1⊊\cdots ⊊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.