Organizations: School Mathematical Sciences, Peking University · Department of Statistics and Data Science, Southern University of Science and Technology · School of Statistics and Data Science, Zhejiang Gongshang University · School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen · Shenzhen Loop Area Institute
Many real-world tasks involve making sequential decisions about whether to select candidates before their responses of interest are revealed. In this work, we address the online selection problem in the context of hierarchical data, where candidates arrive sequentially from different populations. This extends existing online conformal selection frameworks beyond the standard i.i.d./exchangeable data assumption. The primary challenge lies in constructing valid statistics for each candidate sequentially under the hierarchical data structure. To this end, we first develop Online Hierarchical Selection (OHS), a distribution-free method that enables principled candidate selection for hierarchical data streams. Specifically, we introduce methods to construct rank-based e-values for both between-group and within-group samples, and apply averaged e-values to the online e-BH procedure. We then develop OHS with feedback (OHSF), which boosts the power of OHS by leveraging potential response feedback. Theoretically, the proposed methods achieve false discovery rate control under mild hierarchical exchangeability and data arrival assumptions at any time. We also generalize methods to broader settings, such as data with covariate shift and selection under effect-related responses. Extensive experiments on both simulated and real-world datasets demonstrate the effectiveness of the proposed methods.
Figures & tables
Figure 1: FDR for the OHS simulation at K=400 . Columns vary Δ and rows vary α . Error bars give pointwise 95% Monte Carlo intervals for OHS-CU. Dotted horizontal lines show target FDR.
Figure 2: Power for the OHS simulation at K=400 . Columns vary Δ and rows vary α . Error bars give pointwise 95% Monte Carlo intervals for OHS-CU.
Figure 3: FDR for the feedback simulation at K=400 . Columns vary Δ and rows vary α . Error bars give pointwise 95% Monte Carlo intervals for OHSF. Dotted horizontal lines show target FDR.
Figure 4: Power for the feedback simulation at K=400 . Columns vary Δ and rows vary α . Error bars give pointwise 95% Monte Carlo intervals for OHSF.
Figure 5: PRSA: empirical FDR and power at α=0.05 over 600 paired confirmation repetitions. Error bars are pointwise 95% Monte Carlo intervals for OHS-U and OHSF. The dotted line is the FDR target.
Figure 6: KIBA at c=10.5 : empirical FDR and power at α=0.05 over 600 paired confirmation repetitions. Error bars and the dotted line have the same meanings as in Figure 5 .
We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one success'' is identified with a pre-specified target probability $φ$. While traditional online conformal prediction focuses on maintaining validity for the observed sequence, minimizing the resource cost (efficiency) of such selections, especially under limited feedback, remains a significant challenge. In this work, we consider settings with the most limited bandit'' feedback, and demonstrate that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable, is both adversarially valid, ensuring the success target is met on average for any input sequence (and hence under distribution shifts), and stochastically efficient, achieving sublinear efficiency regret for i.i.d. inputs against an appropriate stochastic benchmark. We show such guarantees under canonical models capturing bandit and semi-bandit feedback to the agent via a unifying algorithmic technique, and analytic framework involving Lyapunov functions. Our approach handles more complex settings than prior work, while requiring significantly less feedback, and our results provide a new theoretical bridge between efficient online learning with limited feedback and distribution-free uncertainty quantification.
We study data-driven score construction in conformal selection, which uses conformal p-values and multiple testing to select "interesting" instances with large unobserved labels from a pool of unlabeled data, while controlling the FDR in finite sample. While existing solutions require the score function to be constructed independent of the calibration and test data, it is desirable to select or construct powerful conformity score in a data-driven manner and to leverage all labeled data for score training when presented with many score choices and limited labeled data. We propose Optimized Conformal Selection (OptCS), a general framework that allows valid multiple testing after flexible data-driven score construction. We introduce general conditions under which OptCS constructs valid conformal p-values despite substantial data reuse and handles complex p-value dependencies to maintain finite-sample FDR control. We instantiate this general recipe to propose three FDR-controlling procedures, each optimizing the models differently: (i) selecting a powerful score function among multiple candidates, (ii) training the score with all labeled data without sample splitting, and (iii) combining full-sample training and model selection. We demonstrate the efficacy of our methods via simulation studies and real applications in drug discovery and large language models.
Tian Bai, Ying Jin
Department of Mathematics and Statistics, McGill University · Data Science Initiative and Department of Health Care Policy, Harvard University
Conformalized selection has been widely applied to select high-quality candidates from large datasets with rigorous uncertainty quantification, such as reliable labeling, drug discovery, and the alignment of large language models. Nevertheless, existing methods assume clean responses on calibration data, an assumption that rarely holds in practice. In this paper, we formulate the above tasks as selecting candidates with true predicted labels or with responses exceeding certain values. We demonstrate that existing conformal selection methods fail to control the false discovery rate (FDR) or suffer from severe power loss under contaminated calibration data. To that end, we propose Robust Conformalized Selection (RCS), a unified framework for selective classification with valid FDR control under general label contamination. The key insight of RCS lies in a novel statistical reduction: by separately conditioning on different classes, we translate the intractable label noise into a localized covariate shift problem, which then enables a covariate-adjusted empirical-Bayes-type estimate of the number of false selections. Statistical properties such as the asymptotic FDR control, power optimality, and robustness of RCS are established. We further develop an instantiation of RCS under randomized response model, and also apply RCS to the task of selecting candidates with large response values. Extensive experiments on both simulated and real-world datasets demonstrate the effectiveness of RCS.
Chengyao Yu, Hongxin Wei, Bingyi Jing
Department of Statistics and Data Science Southern University of Science and Technology Shenzhen 518055, China · School of Artificial Intelligence The Chinese University of Hong Kong, Shenzhen Shenzhen Loop Area Institute Shenzhen 518172, China