Constrained Robust Submodular Partitioning
Constrained Robust Submodular Partitioning
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shengjie Wang;Tianyi Zhou;Chandrashekhar Lavania;J. Bilmes
中科院分区：
文献类型：
--
作者：
Shengjie Wang;Tianyi Zhou;Chandrashekhar Lavania;J. Bilmes
在健壮子模块划分问题中，我们的目标是将一组项目分配到m个块中，从而最大化根据子模函数对最小块的评估。健壮的子模块分区促进了分区中每个块的多样性。它在机器学习中有许多应用，例如，为了分布式训练而划分数据，以便在每个块上计算的梯度是一致的。我们研究了在每个块上带有附加约束(例如基数、多拟阵和/或背包)的健壮子模划分问题的一个扩展。例如，在对数据进行分区以进行分布式训练时，可以在每个分区块中添加每个类的样本数相同的约束，以确保数据平衡。我们提出了两类算法，即基于最小块贪婪的算法(具有⌦(1/m)界)和基于轮询的贪婪算法(具有恒定界)，并证明了在各种约束下，它们仍然具有良好的逼近保证。有趣的是，虽然后者通常只在弱多项式时间内运行，但我们证明了将两者结合使用可在保持逼近保证的情况下产生强多项式时间。最后，将算法应用于一个实际的机器学习数据划分问题，取得了较好的效果。
In the robust submodular partitioning problem, we aim to allocate a set of items into m blocks, so that the evaluation of the minimum block according to a submodular function is maximized. Robust submodular partitioning promotes the diversity of every block in the partition. It has many applications in machine learning, e.g., partitioning data for distributed training so that the gradients computed on every block are consistent. We study an extension of the robust submodular partition problem with additional constraints (e.g., cardinality, multiple matroids, and/or knapsack) on every block. For example, when partitioning data for distributed training, we can add a constraint that the number of samples of each class is the same in each partition block, ensuring data balance. We present two classes of algorithms, i.e., Min-Block Greedy based algorithms (with an ⌦ (1 /m ) bound), and Round-Robin Greedy based algorithms (with a constant bound) and show that under various constraints, they still have good approximation guarantees. Interestingly, while normally the latter runs in only weakly polynomial time, we show that using the two together yields strongly polynomial running time while preserving the approximation guarantee. Lastly, we apply the algorithms on a real-world machine learning data partitioning problem showing good results.