Simultaneous Confidence Bounds for Aggregated Effects via Exact Subset Optimization

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.

Scientists and engineers often run many small tests at once — checking whether a new feature helps dozens of customer segments, combining results from many independent studies, or seeing whether one AI method beats another across many datasets. A tempting shortcut is to look at all the results, pick the group of tests that looks most promising, and then report their combined effect. But cherry-picking the best-looking group after seeing the data makes the combined result seem stronger than it truly is, producing claims that later fall apart. We developed a way to report an honest, guaranteed range for such combined effects that stays trustworthy even when the group was chosen by peeking at the data. The catch is that honesty requires accounting for the luckiest-looking group the data could possibly have produced, among an astronomical number of candidates; we show this seemingly impossible search can be solved exactly by recasting it as finding the densest cluster in a network, plus a fast approximate version for very large problems. The result lets practitioners report combined findings that are simultaneously tight and trustworthy.