Lazier Than Lazy Greedy
Open accessThe DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Finding groups in data: an introduction to cluster analysis
(1991) · Choice Reviews Online · doi:10.5860/choice.28-4558 · Cited by 10,474
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326 · cited 1×
“It has also found numerous applications in machine learning and artificial intelligence such as influence maximization (Kempe, Kleinberg, and Tardos 2003 Krause 2011).”
MethodAn analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
Cost-effective outbreak detection in networks
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281239 · Cited by 2,502 · cited 5×
“For this purpose, accelerated/lazy variants (Minoux 1978; Leskovec et al. 2007) of the celebrated greedy algorithm of Nemhauser, Wolsey, and Fisher (1978) have been extensively used.”
BackgroundMethodInfluentialSelf-citation80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition
Torralba, A., Fergus, R., & Freeman, W. T. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.128 · Cited by 1,921
A Class of Submodular Functions for Document Summarization
Lin, H. Z., & Bilmes, J. (2011) · Cited by 972
Accelerated greedy algorithms for maximizing submodular set functions
Minoux, M. (2005) · Springer eBooks · doi:10.1007/bfb0006528 · Cited by 559
Best Algorithms for Approximating the Maximum of a Submodular Set Function
Nemhauser, G. L., & Wolsey, L. A. (1978) · Mathematics of Operations Research · doi:10.1287/moor.3.3.177 · Cited by 538 · cited 1×
“…would like to choose a summary of a manageable size, a natural optimization problem is to find a sum-mary A ∗ of size at most k that maximizes the utility, i.e., (1) Unfortunately, this optimization problem is NP-hard for many classes of submodular functions (Nemhauser and Wolsey 1978; Feige 1998).”
BackgroundMulti-document Summarization via Budgeted Maximization of Submodular Functions
Lin, H. Z., & Bilmes, J. (2010) · North American Chapter of the Association for Computational Linguistics · Cited by 462
Cited by
Deep Metric Learning via Facility Location
Song, H. O., Jegelka, S., Rathod, V., & Murphy, K. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.237 · Cited by 287
Sex differences in the elevated plus-maze test and large open field test in adult Wistar rats.
Knight, P., Chellian, R., Wilson, R., Behnood-Rod, A., Panunzio, S., & Bruijnzeel, A. W. (2021) · Pharmacology Biochemistry and Behavior · doi:10.1016/j.pbb.2021.173168 · Cited by 252
Ranked List Loss for Deep Metric Learning
Wang, X., Hua, Y., Kodirov, E., Hu, G., Garnier, R., & Robertson, N. M. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00535 · Cited by 242
“As a result, the loss augmented inference and refinement are applied to select facilities (clustering medoids) based on the greedy algorithm [19].”
Method
Metadata
- Authors
- Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrak, J., & Krause, A.
- Venue
- Proceedings of the AAAI Conference on Artificial Intelligence
- Published
- 2015-02-18
- Volume
- 29
- Issue
- 1
- ISSN
- 2159-5399 (ISSN-L)
- 2374-3468
- OpenAlex
- W1757790940
- Cited by
- 159
- References
- 32
- FWCI
- 19.00
- Type
- conference paper
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.