2016/05/31 by Lucic, Mario, Bachem, Olivier, Zadimoghaddam, Morteza +1
#Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1605.09619
A variety of large-scale machine learning problems can be cast as instances of constrained submodular maximization. Existing approaches for distributed submodular maximization have a critical drawback: The capacity - number of instances that can fit in memory - must grow with the data set size. In practice, while one can provision many machines, the capacity of each machine is limited by physical constraints. We propose a truly scalable approach for distributed submodular maximization under fixed capacity. The proposed framework applies to a broad class of algorithms and constraints and provides theoretical guarantees on the approximation factor for any available capacity. We empirically evaluate the proposed algorithm on a variety of data sets and demonstrate that it achieves performance competitive with the centralized greedy solution.