mlsanityData to 7 Oct 2026

Lazier Than Lazy Greedy

arXiv 1409.7938 ↗First posted 28 Sep 2014cs.LG cs.DS cs.IRcited by 97

Not on the map. Why?

Abstract (arXiv)

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-varepsilon) 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.

Key facts. Cited by 97 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Sep 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 19; 2023: 18; 2024: 13; 2025: 10; 2026: 16.

97 papers.

Sort:

By area:

  1. 2021Batch Active Learning at Scalecited by 127
  2. 2021SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarioscited by 83
  3. 2023Data Diversity Matters for Robust Instruction Tuningcited by 76
  4. 2021RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learningcited by 72
  5. 2022Adaptive Second Order Coresets for Data-efficient Machine Learningcited by 60
  6. 2021PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selectioncited by 50
  7. 2023Identifying Spurious Biases Early in Training through the Lens of Simplicity Biascited by 44
  8. 2022Not All Poisons are Created Equal: Robust Training against Data Poisoningcited by 29
  9. 2021TALISMAN: Targeted Active Learning for Object Detection with Rare Classes and Slices using Submodular Mutual Informationcited by 27
  10. 2022Data-Efficient Structured Pruning via Submodular Optimizationcited by 22
  11. 2023Data-Efficient Contrastive Self-supervised Learning: Most Beneficial Examples for Supervised Learning Contribute the Leastcited by 22
  12. 2024An Experimental Design Framework for Label-Efficient Supervised Finetuning of Large Language Modelscited by 22
38 more
  1. 2023Combinatorial Stochastic-Greedy Banditcited by 18
  2. 2025ToMA: Token Merge with Attention for Diffusion Modelscited by 17
  3. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  4. 2024Federated Combinatorial Multi-Agent Multi-Armed Banditscited by 11
  5. 2021Greedy-Based Feature Selection for Efficient LiDAR SLAMcited by 9
  6. 2021Optimal Sampling Gaps for Adaptive Submodular Maximizationcited by 9
  7. 2022Using Partial Monotonicity in Submodular Maximizationcited by 9
  8. 2022CLINICAL: Targeted Active Learning for Imbalanced Medical Image Classificationcited by 9
  9. 2023MILO: Model-Agnostic Subset Selection Framework for Efficient Model Training and Tuningcited by 9
  10. 2021Adaptive Regularized Submodular Maximizationcited by 8
  11. 2022Submodlib: A Submodular Optimization Librarycited by 8
  12. 2023Accelerating Batch Active Learning Using Continual Learning Techniquescited by 8
  13. 2024Improving Robustness to Model Inversion Attacks via Sparse Coding Architecturescited by 8
  14. 2021A Unified Framework for Task-Driven Data Quality Managementcited by 7
  15. 2023Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clusteringcited by 7
  16. 2021Balancing the Budget: Feature Selection and Tracking for Multi-Camera Visual-Inertial Odometrycited by 6
  17. 2022Active Data Discovery: Mining Unknown Data using Submodular Information Measurescited by 6
  18. 2023Deep Active Alignment of Knowledge Graph Entities and Schematacited by 6
  19. 2023Overcome Modal Bias in Multi-modal Federated Learning via Balanced Modality Selectioncited by 6
  20. 2025AdaGReS:Adaptive Greedy Context Selection via Redundancy-Aware Scoring for Token-Budgeted RAGcited by 6
  21. 2021One-Round Active Learningcited by 5
  22. 2022Lazy and Fast Greedy MAP Inference for Determinantal Point Processcited by 5
  23. 2023Maximizing Submodular Functions for Recommendation in the Presence of Biasescited by 5
  24. 2023Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraintcited by 5
  25. 2023Training-Free Neural Active Learning with Initialization-Robustness Guaranteescited by 5
  26. 2026When Self-Evolution Backfires: Pre-Commit Gating against Skill Contamination in LLM Agentscited by 5
  27. 2021DIVINE: Diverse Influential Training Points for Data Visualization and Model Refinementcited by 4
  28. 2021Robust Adaptive Submodular Maximizationcited by 4
  29. 2022Nonmyopic Multiclass Active Search with Diminishing Returns for Diverse Discoverycited by 4
  30. 2022Data-Efficient Augmentation for Training Neural Networkscited by 4
  31. 2024Submodular Framework for Structured-Sparse Optimal Transportcited by 4
  32. 2025Looking Beyond the Known: Towards a Data Discovery Guided Open-World Object Detectioncited by 4
  33. 2021On Meritocracy in Optimal Set Selectioncited by 3
  34. 2022Sparsification of Decomposable Submodular Functionscited by 3
  35. 2022PLATINUM: Semi-Supervised Model Agnostic Meta-Learning using Submodular Mutual Informationcited by 3
  36. 2022Adaptive Control of Client Selection and Gradient Compression for Efficient Federated Learningcited by 3
  37. 2024Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraintcited by 3
  38. 2026Submodular Benchmark Selectioncited by 3

50 most cited of 97 All 97 (JSON)