Simultaneous Confidence Bounds for Aggregated Effects via Exact Subset Optimization

Weihang Xu, Huajie Qian, Wotao Yin, Xinshang WangICML 2026 · OpenReview

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.
BibTeX
@inproceedings{xu2026simultaneous,
  author = {Weihang Xu and Huajie Qian and Wotao Yin and Xinshang Wang},
  title = {{Simultaneous Confidence Bounds for Aggregated Effects via Exact Subset Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=1C2LrZ7SNL},
}

Loading related content...

Figure