The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
复制标题
DOI：
--
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward
中科院分区：
文献类型：
--
作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward
机器学习中的各种问题，包括示例聚类，文档摘要和传感器放置，可以被视为受约束的次复合最大化问题。不幸的是，所得的子管道优化问题通常太大，无法在一台机器上解决。我们考虑了一种分布式贪婪的算法，该算法将以前的方法与随机化结合在一起。结果是一种令人尴尬的平行且实现可证明的，恒定的因素，最差近似保证的算法。在我们的实验中，我们证明了其在具有不同种类的约束的大问题中的效率，其客观值始终接近集中式环境中可实现的目标。
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. We consider a distributed, greedy algorithm that combines previous approaches with randomization. The result is an algorithm that is embarrassingly parallel and achieves provable, constant factor, worstcase approximation guarantees. In our experiments, we demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.