Sample-Efficient "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection
This work seeks to break the sample efficiency bottleneck in 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". This seemingly simple modification achieves the optimal sample complexity reduction for a widely used class of efficient 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 allows for seamless integration with various existing R&S procedures, while achieving optimal sample complexity. Theoretically, we develop a novel gradient analysis framework to analyze sample efficiency and guide the design of large-scale R&S procedures. We also introduce a new parallel clustering algorithm tailored for large-scale scenarios. Finally, in large-scale AI applications such as neural architecture search, our methods demonstrate superior performance.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringNeural Architecture SearchSimilar Papers 제목 키워드 기반
Two provably consistent divide and conquer clustering algorithms for large networks
In this article, we advance divide-and-conquer strategies for solving the community detection problem in networks. We propose two algorithms which perform clustering on a number of small subgraphs and finally patches the…
ClusteringCommunity DetectionVocal Bursts Valence PredictionSpectral Clustering for Divide-and-Conquer Graph Matching
We present a parallelized bijective graph matching algorithm that leverages seeds and is designed to match very large graphs. Our algorithm combines spectral graph embedding with existing state-of-the-art seeded graph ma…
ClusteringGraph EmbeddingGraph MatchingStochastic Block ModelHomogenous and Heterogenous Parallel Clustering: An Overview
Recent advances in computer architecture and networking opened the opportunity for parallelizing the clustering algorithms. This divide-and-conquer strategy often results in better results to centralized clustering with …
Clustering$DC^2$: A Divide-and-conquer Algorithm for Large-scale Kernel Learning with Application to Clustering
Divide-and-conquer is a general strategy to deal with large scale problems. It is typically applied to generate ensemble instances, which potentially limits the problem size it can handle. Additionally, the data are ofte…
ClusteringDistributed sequential method for analyzing massive data
To analyse a very large data set containing lengthy variables, we adopt a sequential estimation idea and propose a parallel divide-and-conquer method. We conduct several conventional sequential estimation procedures sepa…