The Library
The power of randomization : distributed submodular maximization on massive datasets
Tools
Barbosa, Rafael da Ponte, Ene, Alina, Nguyen, Huy L. and Ward, Justin (2015) The power of randomization : distributed submodular maximization on massive datasets. In: 32nd International Conference on Machine Learning, Lille, France, 06-11 Jul 2015. Published in: Proceedings of the 32nd International Conference on Machine Learning, 37 pp. 1236-1244. doi:10.5555/3045118.3045250
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: https://doi.org/10.5555/3045118.3045250
Abstract
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, 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.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Submodular functions, Combinatorial optimization, Machine learning | ||||||||
Journal or Publication Title: | Proceedings of the 32nd International Conference on Machine Learning | ||||||||
Publisher: | ML Research Press | ||||||||
Official Date: | 2015 | ||||||||
Dates: |
|
||||||||
Volume: | 37 | ||||||||
Page Range: | pp. 1236-1244 | ||||||||
DOI: | 10.5555/3045118.3045250 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
Grant number: | EP/J021814/1 | ||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | 32nd International Conference on Machine Learning | ||||||||
Type of Event: | Conference | ||||||||
Location of Event: | Lille, France | ||||||||
Date(s) of Event: | 06-11 Jul 2015 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |