Source-linked AI summary
Lazier Than Lazy Greedy
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, Andreas Krause
TL;DR
The paper asks whether monotone submodular maximization can be made faster than lazy greedy without sacrificing utility. It introduces STOCHASTIC-GREEDY, a randomized cardinality-constrained algorithm with a (1−1/e−ε) expected approximation and k-independent linear-time evaluation cost, and reports comparable utility at substantially lower practical cost.
Problem
Large-scale data makes expensive function evaluations problematic, while standard greedy maximization requires O(n · k) evaluations and LAZY-GREEDY has unknown exact cost.
Method
STOCHASTIC-GREEDY samples a set of size (n/k) log(1/ε), which overlaps the optimum with probability 1−ε, to obtain greedy-like improvement more cheaply.
Results
STOCHASTIC-GREEDY achieves a (1−1/e−ε) expected approximation with O(n log(1/ε)) evaluations independent of k, while experiments report similar utility to LAZY-GREEDY at much lower cost.
Takeaways & Limitations
STOCHASTIC-GREEDY is presented as suitable for very large-scale submodular optimization and compatible with distributed frameworks that use LAZY-GREEDY.
Abstract
from arXiv · showhide
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.
Introduction
Large, complex datasets motivate computationally tractable data summarization, modeled as cardinality-constrained monotone submodular maximization. Greedy methods offer strong guarantees but can require too many expensive function evaluations, motivating faster alternatives.
- Motivation: Large, diverse, feature-rich datasets create computational challenges for data-intensive inference.Data summarization is presented as a way to exploit such data while improving analytics efficiency and scalability.
- Submodular Modeling: Data summarization selects a manageable-size representative set using a utility measure for representativeness.The utility depends on the application, such as entropy for random variables or subspace dimension for vectors.
- Submodular Modeling: Submodularity formalizes diminishing returns: adding an element can be more beneficial to a smaller set than to a superset.The marginal gain Δ(i|A) measures the utility increase from adding element i to summary A.
- Greedy Optimization: (1−1/e) is the approximation guarantee provided by greedy maximization for non-negative monotone submodular functions.The greedy algorithm repeatedly adds the element with maximum marginal gain, but requires O(n · k) function evaluations.
- Greedy Optimization: LAZY-GREEDY accelerates greedy selection by maintaining upper bounds on marginal gains and re-evaluating candidates until the best choice is certified.Although its exact evaluation cost is unknown, LAZY-GREEDY achieves large practical speedups and is widely used.
- Paper Contribution: STOCHASTIC-GREEDY provides a (1−1/e−ε) approximation in O(n log(1/ε)) function evaluations, independent of k.The paper presents it as the first linear-time algorithm for this general cardinality-constrained setting.
Related Work
Prior work applied submodular optimization broadly and pursued scaling through lazy, distributed, streaming, and multistage methods. STOCHASTIC-GREEDY complements these approaches by replacing LAZY-GREEDY subroutines with a method having k-independent evaluation cost.
- Applications: Submodular optimization generalizes problems including maximum weighted matching, max coverage, and facility location, with applications across artificial intelligence and machine learning.Applications include influence maximization, information gathering, document summarization, and active learning.
- Lazy Greedy: Accelerated or lazy variants of greedy have been extensively used to handle increasingly large datasets.These methods are established tools across submodular optimization applications.
- Scaling Up: Distributed methods addressed maximum coverage with constant-factor approximations, while later work treated more general submodular functions with bounded marginal gains.These approaches target scaling through parallel or distributed computation.
- Scaling Up: Streaming approaches ranged from heuristic methods requiring strong data-stream assumptions to a one-pass method with a constant-factor guarantee for general submodular functions.The latter removed assumptions about how the data stream is generated.
- Integration: STOCHASTIC-GREEDY can replace LAZY-GREEDY in existing distributed algorithms and thereby improve the efficiency of larger algorithmic frameworks.The paper describes this relationship as complementary to prior distributed and streaming work.
- Multistage Methods: MULTI-GREEDY used multiple stages to reduce LAZY-GREEDY runtime by approximating the underlying submodular function.The cited comparison reports that STOCHASTIC-GREEDY uses O(n log(1/ε)) evaluations versus O(n/ε log(n/ε)) for MULTI-GREEDY and performs better empirically.
STOCHASTIC-GREEDY Algorithm
STOCHASTIC-GREEDY accelerates monotone submodular maximization by sampling a small random candidate set at each iteration, while retaining a near-optimal expected approximation guarantee independent of k.
- Algorithm: Subsampling works because a random sample of size (n/k) log(1/ε) overlaps the optimum with probability 1−ε.Submodularity then provides the same gap-reduction improvement as selecting an appropriate optimum element in expectation.
- Algorithm: STOCHASTIC-GREEDY samples (n/k) log(1/ε) elements uniformly at each iteration and adds the sampled element with the largest marginal gain.It starts from the empty set and repeats this process for k iterations.
- Guarantees: O(n log(1/ε)) function evaluations give an expected (1−1/e−ε) approximation to the optimum, independent of the cardinality constraint.The evaluation bound follows from k iterations, each examining at most (n/k) log(1/ε) sampled elements.
- Lazy evaluation: Lazy evaluation further reduces evaluations by reusing marginal gains and exploiting stable element orderings within each random sample.Submodularity certifies the sampled element as best when its updated upper bound remains at least as large as the others.
Experimental Results
Experiments evaluate STOCHASTIC-GREEDY across nonparametric learning, exemplar-based clustering, and sensor placement, finding near-maximal utility at substantially lower computational cost than benchmark methods.
- Experimental setup: The experiments compare STOCHASTIC-GREEDY with RANDOM-SELECTION, SAMPLE-GREEDY, THRESHOLD-GREEDY, and LAZY-GREEDY across three machine-learning applications.The applications are nonparametric learning, exemplar-based clustering, and sensor placement.
- Nonparametric Learning: The nonparametric-learning application uses Gaussian Processes, where selecting a small active set avoids the expensive matrix inversion required for direct prediction.The active-set objective is an information-gain function that is monotone submodular.
- Nonparametric Learning: In nonparametric learning, STOCHASTIC-GREEDY achieves practically identical utility to LAZY-GREEDY with much lower computational cost.Decreasing ε increases utility while increasing computational cost, producing utility–cost tradeoffs across benchmarks.
- Exemplar-based clustering: Exemplar-based clustering maximizes a monotone submodular transformation of the k-medoid objective, converting dissimilarity minimization into utility maximization.The summary-size increase makes the underlying problem computationally challenging.
- Exemplar-based clustering: In exemplar-based clustering, STOCHASTIC-GREEDY outperforms benchmarks with significantly lower computational cost and reaches near-maximal utility at lower cost.The experiment uses 10,000 Tiny Images and Euclidean dissimilarity.
- Large-scale experiment: On 50,000 Tiny Images, STOCHASTIC-GREEDY outperforms SAMPLE-GREEDY in both utility and cost and is faster than the only practical comparison method.LAZY-GREEDY and THRESHOLD-GREEDY could not be run on this larger dataset.
- Sensor Placement: Sensor placement selects locations to reduce expected contaminant-detection penalties, using a monotone submodular objective.The setting is motivated by monitoring spatial phenomena with a limited number of sensors.
- Sensor Placement: In sensor placement, STOCHASTIC-GREEDY achieves near-maximal utility at much lower cost than the other benchmarks.The experiment uses a 12,527-node distribution network from the BWSN challenge.
Conclusion
The paper presents STOCHASTIC-GREEDY as a linear-time algorithm for cardinality-constrained monotone submodular maximization, independent of k. It reports near-optimal approximation with substantially lower computational cost and broader scalability benefits.
- STOCHASTIC-GREEDY is the first linear-time algorithm for cardinality-constrained submodular maximization with no dependence on k.
- 1 −1/e −ε approximation is achieved using n log 1/ε function evaluations.
- STOCHASTIC-GREEDY achieves a major fraction of function utility with much less computational cost in extensive experiments.
- The improvement can also benefit parallel or decomposed frameworks that use greedy subroutines, supporting large-scale optimization.
Appendix, Analysis
The analysis bounds STOCHASTIC-GREEDY’s expected one-step progress by sampling from the remaining elements and derives the stated approximation guarantee by induction. The proof concludes with the bound 1 −1/e −ε.
- The approximation guarantee follows from a lemma stating a lower bound on STOCHASTIC-GREEDY’s expected gain in one step.
- The algorithm samples s = n/ε elements from V \ A and selects the sampled element with maximum marginal value.
- The sampled set is analyzed through the probability that it intersects the still-unselected part of the optimum solution.
- The expected-gain recurrence is applied to the iterates A_i, with expectations and induction completing the proof.
- 1 −e^−(1−ε) f(A∗) is lower-bounded by (1 −1/e −ε)f(A∗).