# Sample-Efficient "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection

arXiv: https://arxiv.org/abs/2402.02196 · HTML: https://mlsanity.com/paper/2402.02196/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 52 references that are in the map.
- First posted on arXiv 3 Feb 2024.

## Builds on (most cited first, 10 of 10)

- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [Single Path One-Shot Neural Architecture Search with Uniform Sampling](https://mlsanity.com/paper/1904.00420/) (2019)
- [Review on Ranking and Selection: A New Perspective](https://mlsanity.com/paper/2008.00249/) (2020)
- [Uncertainty Quantification and Exploration for Reinforcement Learning](https://mlsanity.com/paper/1910.05471/) (2019)
- [Ranking and Selection with Covariates for Personalized Decision Making](https://mlsanity.com/paper/1710.02642/) (2017)
- [Sample and Computationally Efficient Stochastic Kriging in High Dimensions](https://mlsanity.com/paper/2010.06802/) (2020)
- [Efficient Ranking and Selection in Parallel Computing Environments](https://mlsanity.com/paper/1506.04986/) (2015)
- [Analyzing and provably improving fixed budget ranking and selection algorithms](https://mlsanity.com/paper/1811.12183/) (2018)
- [Gradient-based Algorithms for Convex Discrete Optimization via Simulation](https://mlsanity.com/paper/2010.16250/) (2020)
- [A Contextual Ranking and Selection Method for Personalized Medicine](https://mlsanity.com/paper/2206.12640/) (2022)

## Built on by (most cited first, 2 of 2)

- [An Agglomerative Clustering of Simulation Output Distributions Using Regularized Wasserstein Distance](https://mlsanity.com/paper/2407.12100/) (2024)
- [New Additive OCBA Procedures for Robust Ranking and Selection](https://mlsanity.com/paper/2412.06020/) (2024)

## Abstract (arXiv)

This work aims to improve the sample efficiency of parallel large-scale ranking and selection (R&S) problems by leveraging correlation information. We modify the commonly used "divide and conquer" framework in parallel computing by adding a correlation-based clustering step, transforming it into "clustering and conquer". Theoretically, we develop a novel gradient-based analysis framework and show that this seemingly simple modification substantially improves the performance of large-scale R&S procedures. Our approach enjoys two key advantages: (1) it does not require highly accurate correlation estimation or precise clustering, and (2) it can be seamlessly integrated with various existing fixed-precision and fixed-budget R&S procedures while achieving optimal sample complexity. We also introduce a new parallel clustering algorithm tailored to large-scale settings. Finally, in large-scale AI applications such as neural architecture search, our methods demonstrate superior performance.