Sample-Efficient Clustering and Conquer Procedures for Parallel Large-Scale Ranking and Selection
<|reference_start|>Sample-Efficient Clustering and Conquer Procedures for Parallel Large-Scale Ranking and Selection: We propose novel "clustering and conquer" procedures for the parallel large-scale ranking and selection (R&S) problem, which leverage correlation information for clustering to break the bottleneck of sample efficiency. In parallel computing environments, correlation-based clustering can achieve an $\mathcal{O}(p)$ sample complexity reduction rate, which is the optimal reduction rate theoretically attainable. Our proposed framework is versatile, allowing for seamless integration of various prevalent R&S methods under both fixed-budget and fixed-precision paradigms. It can achieve improvements without the necessity of highly accurate correlation estimation and precise clustering. In large-scale AI applications such as neural architecture search, a screening-free version of our procedure surprisingly surpasses fully-sequential benchmarks in terms of sample efficiency. This suggests that leveraging valuable structural information, such as correlation, is a viable path to bypassing the traditional need for screening via pairwise comparison--a step previously deemed essential for high sample efficiency but problematic for parallelization. Additionally, we propose a parallel few-shot clustering algorithm tailored for large-scale problems.<|reference_end|>
@article{zhang2024sample-efficient,
    title={Sample-Efficient Clustering and Conquer Procedures for Parallel
  Large-Scale Ranking and Selection},
    author={Zishi Zhang, Yijie Peng},
    journal={arXiv preprint arXiv:2402.02196},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.02196},
    primaryClass={stat.ME cs.LG}
}