Sample-Optimal Large-Scale Optimal Subset Selection
<|reference_start|>Sample-Optimal Large-Scale Optimal Subset Selection: Ranking and selection (R&S) conventionally aims to select the unique best alternative with the largest mean performance from a finite set of alternatives. However, for better supporting decision making, it may be more informative to deliver a small menu of alternatives whose mean performances are among the top $m$. Such problem, called optimal subset selection (OSS), is generally more challenging to address than the conventional R&S. This challenge becomes even more significant when the number of alternatives is considerably large. Thus, the focus of this paper is on addressing the large-scale OSS problem. To achieve this goal, we design a top-$m$ greedy selection mechanism that keeps sampling the current top $m$ alternatives with top $m$ running sample means and propose the explore-first top-$m$ greedy (EFG-$m$) procedure. Through an extended boundary-crossing framework, we prove that the EFG-$m$ procedure is both sample optimal and consistent in terms of the probability of good selection, confirming its effectiveness in solving large-scale OSS problem. Surprisingly, we also demonstrate that the EFG-$m$ procedure enables to achieve an indifference-based ranking within the selected subset of alternatives at no extra cost. This is highly beneficial as it delivers deeper insights to decision-makers, enabling more informed decision-makings. Lastly, numerical experiments validate our results and demonstrate the efficiency of our procedures.<|reference_end|>
@article{li2024sample-optimal,
    title={Sample-Optimal Large-Scale Optimal Subset Selection},
    author={Zaile Li, Weiwei Fan, L. Jeff Hong},
    journal={arXiv preprint arXiv:2408.09537},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.09537},
    primaryClass={stat.ML cs.LG stat.ME}
}