Many learning problems hinge on the fundamental problem of subset selection,
i.e., identifying a subset of important and representative points. For example,
selecting the most significant samples in ML training cannot only reduce
training costs but also enhance model quality. Submodularity, a discrete
analogue of convexity, is commonly used for solving 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 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 show that these algorithms 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.

通过提出一种新颖的分布式界限算法，并使用多轮基于分区的分布式贪心算法，此论文解决了子集选择问题，能够在没有或极小损失质量的情况下，找到高质量的子集。