2024/02/26 by Maximilian Böther, Böther, Maximilian, Sebastian Abraham +7
Computer Science · #Artificial Intelligence (cs.AI) #Computer Vision and Pattern Recognition (cs.CV) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning and ELM #Neural Networks and Applications #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2402.16442
openalex publication_date 2024/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Modern datasets span billions of samples, making training on all available data infeasible. Selecting a high quality subset helps in reducing training costs and enhancing model quality. Submodularity, a discrete analogue of convexity, is commonly used for solving such subset selection problems. However, existing algorithms for optimizing submodular functions are sequential, and the prior distributed methods require at least one central machine to fit the target subset in DRAM. At billion datapoint scale, even the subset may not fit a single machine, and the sequential algorithms are prohibitively slow. In this paper, we relax the requirement of having a central machine for the target subset by proposing a novel distributed bounding algorithm with provable approximation guarantees. The algorithm iteratively bounds the minimum and maximum utility values to select high quality points and discard the unimportant ones. When bounding does not find the complete subset, we use a multi-round, partition-based distributed greedy algorithm to identify the remaining subset. We discuss how to implement these algorithms in a distributed data processing framework and empirically analyze different configurations. We find high quality subsets on CIFAR-100 and ImageNet with marginal or no loss in quality compared to centralized methods, and scale to a dataset with 13 billion points.