Lazier Than Lazy Greedy

By Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondr'ak, Andreas Krause. 2014

472 citations recorded by the source corpus.

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 maximizing a general monotone submodular function subject to a cardinality constraint. We show that our randomized algorithm, STOCHASTIC-GREEDY, can achieve a (1 − 1/e − ε) approximation guarantee, in expectation, to the optimum solution in time linear in the size of the data and independent of the cardinality constraint. We empirically demonstrate the effectiveness 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 scenarios STOCHASTIC-GREEDY does not evaluate the whole fraction of data points even once and still achieves indistinguishable results compared to lazy greedy.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, background): “G REEDY [Mirzasoleiman et al., 2015], further reduces the cost to , or equivalently O (log(1 /(cid:15) )) forward passes in layer (cid:96) + 1 with a batch of size n , while maintaining almost the same approximation guarantee (1 − e − γ ˆ S,k − (cid:15) ) in expectation.”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, background): “Algorithmic advances of this kind include Stochastic-Greedy [Mirzasoleiman et al., 2015], Sieve-Streaming [Badanidiyuru et al., 2014], and several distributed approaches [Mirzasoleiman et al., 2013; Barbosa et al., 2015, 2016; Pan et al., 2014; Khanna et al., 2017].”
RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning (2021, methodology): “Further, Theorem 1 implies that the optimization problem given in Equation (5) can be solved efficiently using greedy algorithms [37, 38] with approximation guarantees.”
Deep Metric Learning via Facility Location (2016, background): “Yet, if need be, we can speed up this part via a stochastic version of the greedy algorithm [22].”
Submodular Maximization in Clean Linear Time (2020, methodology): “In their seminal works, Nemhauser and Wolsey [56] and Nemhauser et al. [57] showed that a greedy algorithm achieves a tight 1 − 1 /e approximation guarantee for maximizing a monotone submodualr function subject to cardinality constraint ( SMC ).”
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity (2018, methodology): “We note that, due to known lower bounds [BS18, MBK + 15], the query complexity of the algorithm is optimal up to factors of 1 /ε and the adaptivity is optimal up to factors of 1 / log log( n ) and 1 /ε .”
Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “However, its running time can be reduced to O ( | V | ) using stochastic algorithms (Mirzasoleiman et al., 2015a) and further improved using lazy evaluation (Minoux, 1978), and distributed implementations (Mirzasoleiman et al., 2015b; 2016).”
Restricted Strong Convexity Implies Weak Submodularity (2016, background): “Therefore, several recent algorithms improve efficiency at the expense of slightly weaker guarantees [4, 16, 27, 36, 42].”
GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning (2020, background): “Except for negative squared loss, the submodular functions for all other losses (including cross-entropy) are monotone, and hence the lazy greedy (Minoux 1978) or stochastic greedy (Mirzasoleiman et al. 2014) give 1−1/e approximation guarantees.”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, methodology): “It uses the same distorted objective as DISTORTED GREEDY, but enjoys an asymptotically faster run time due to sampling techniques of (Mirzasoleiman et al., 2015).”
Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten" (2017, methodology): “Hence, we have: STOCHASTIC-GREEDY (SG): Similar to the the greedy algorithm, STOCHASTIC-GREEDY starts with an empty set and adds one element at each iteration until obtains a solution of sizem.”