Simultaneous Confidence Bounds for Aggregated Effects via Exact Subset Optimization

Abstract

We study simultaneous confidence bounds for aggregated effects over downward-closed subset families of independent statistical tests. The bounds are obtained by bootstrap calibration of the maximum normalized aggregated effect over the relevant subset family, yielding valid post-hoc inference for data-selected subsets and tighter bounds than classical methods that protect all linear contrasts. A central challenge is that the required maximization is a nonlinear combinatorial optimization problem. We cast it as a weighted densest-subgraph problem and derive exact linear and mixed integer linear program reformulations, and we further develop a fully polynomial-time approximation scheme that exploits the rank-1 structure of the objective to scale to large families. On the statistical side, we establish a finite-sample coverage guarantee with a lighter dependence on the subset family size than high-dimensional central limit theorems provide. We illustrate the method on synthetic and real machine learning applications.