Scaling Submodular Optimization with Lazy Greedy Selection

This direction is split into other directions: lazy greedy optimization. Its last version stays readable and citable here.

Version 1 of 147 papers51 conceptsfrozen 2026-10-04

In many real-world problems—from placing sensors in a city to selecting a diverse set of social media posts—we face a common challenge: we want to pick a subset of items that provides the most "benefit," but we are limited by a budget. These problems often exhibit a mathematical property called submodularity, or the law of diminishing returns.

As Andreas Krause and Carlos Guestrin demonstrated in Near-optimal Observation Selection using Submodular Functions, submodularity allows us to turn NP-hard problems into manageable tasks. While a simple "greedy" algorithm—picking the best item one by one—is theoretically near-optimal, it is often too slow for large-scale data. The research direction explored here focuses on lazy evaluation, a mechanism that leverages the structure of submodularity to achieve massive speedups without losing accuracy.

The Intuition of Diminishing Returns

A function is submodular if adding an element to a small set helps more than (or equal to) adding that same element to a larger set. Imagine placing a weather sensor: the first sensor in a park provides a lot of new information. The tenth sensor in that same park provides very little.

The standard way to maximize such a function is the Greedy Algorithm:

  1. Start with an empty set.
  2. Look at every remaining item.
  3. Calculate how much "extra" value (marginal gain) each item adds.
  4. Pick the item with the highest marginal gain.
  5. Repeat until the budget is full.

The bottleneck is step 2. If you have 1 million items and want to pick 1,000, you might have to perform nearly a billion function evaluations. In fields like robotics or social network analysis, where evaluating a single "gain" might involve complex simulations or graph traversals, this is computationally ruinous.

The Lazy Greedy Mechanism

The core breakthrough in this research area is the realization that we don't actually need to re-evaluate every item at every step. Because of submodularity, we know one crucial fact: the marginal gain of an item can never increase as our set grows.

If an item added 10 units of value when our set was empty, it will add at most 10 units of value now that we have picked other items. This allows us to use the previous marginal gain as an upper bound.

As described by Niv Buchbinder and Roy Schwartz in Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization, the "Lazy Greedy" algorithm (often called CELF) works by maintaining a priority queue of these upper bounds:

  1. Sort: Put all items in a priority queue based on their initial marginal gains.
  2. Pop: Take the top item from the queue.
  3. Re-evaluate: Since the set has changed, calculate its actual current marginal gain.
  4. Check: If its new gain is still higher than the old gain of the second item in the queue, it must be the best choice. We don't need to look at anything else.
  5. Re-insert: If it's not the best, put it back in the queue with its updated value and repeat.

This simple trick allows algorithms to skip the vast majority of computations. In Incorporating Diversity into Influential Node Mining, Jiawei Han and colleagues showed that this approach can lead to a 1,000x speedup over traditional greedy methods while maintaining the same influence spread.

Beyond Static Sets: Adaptive Submodularity

The real world is rarely static. Often, we make a choice, observe the outcome, and then decide what to do next. Andreas Krause and Daniel Golovin extended the lazy greedy intuition to these scenarios in Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization.

In adaptive submodularity, we maximize the expected marginal gain. The lazy evaluation strategy still holds: by maintaining upper bounds on expected benefits, we can navigate high-dimensional state spaces—like a robot deciding where to move to best localize an object—without exhaustive search. This is further explored in Sequential Decision Making in Computational Sustainability via Adaptive Submodularity, where the authors apply these "greedy" policies to complex conservation planning.

Broad Applications and Scalability

The beauty of the lazy greedy framework is its versatility. Researchers have applied these pruning and priority-queue techniques to a wide array of domains:

By treating the "diminishing returns" property not just as a theoretical curiosity but as a tool for computational pruning, this research direction has transformed submodular maximization from a slow, iterative process into a high-performance engine for modern AI.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_submodular_optimization_with_laz_018de320,
  title = {Scaling Submodular Optimization with Lazy Greedy Selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-submodular-optimization-with-lazy-greedy-selection/rdr_018de32073134938933b9b52a086b9a5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_submodular_optimization_with_laz_018de320_v1,
  title = {Scaling Submodular Optimization with Lazy Greedy Selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-submodular-optimization-with-lazy-greedy-selection/rdr_018de32073134938933b9b52a086b9a5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}