The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
This work addresses the scalability issue for practitioners dealing with massive datasets in submodular optimization, though it is incremental as it builds on existing distributed methods.
The paper tackles the challenge of solving large-scale constrained submodular maximization problems, which are common in machine learning tasks like clustering and summarization, by developing a distributed algorithm that achieves constant-factor approximation guarantees and demonstrates efficiency in experiments with objective values close to centralized results.
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 develop a simple distributed algorithm that is embarrassingly parallel and it achieves provable, constant factor, worst-case 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.