Lazier Than Lazy Greedy

Is it possible to maximize a monotone submodular function faster than the widely used lazy greedy algorithm (also known as accelerated greedy), both in theory and practice? In this paper, we develop the first linear-time algorithm for maxi-mizing a general monotone submodular function subject to a cardinality constraint. We show that our randomized algo-rithm, STOCHASTIC-GREEDY, can achieve a (1 − 1/e − ε) approximation guarantee, in expectation, to the optimum so-lution in time linear in the size of the data and independent of the cardinality constraint. We empirically demonstrate the ef-fectiveness of our algorithm on submodular functions arising in data summarization, including training large-scale kernel methods, exemplar-based clustering, and sensor placement. We observe that STOCHASTIC-GREEDY practically achieves the same utility value as lazy greedy but runs much faster. More surprisingly, we observe that in many practical scenar-ios STOCHASTIC-GREEDY does not evaluate the whole frac-tion of data points even once and still achieves indistinguish-able results compared to lazy greedy