Lazy Greedy: Speeding Up Submodular Maximization for Free

In Part 2, I introduced the greedy algorithm for maximizing a monotone submodular function $f$ under a cardinality constraint $k$ , and showed that it achieves a $(1 - 1/e) \approx 0.632$ approximation ratio, provably the best any polynomial-time algorithm can do. The best possible approximation ratio, however, doesn’t mean the best possible runtime. The algorithm costs $\mathcal{O}(n \cdot k)$ calls to the value oracle for $f$ : at each of the $k$ steps, it recomputes the marginal gain $f(e \mid S_{j-1})$ for every remaining element $e \in \mathcal{V} \setminus S_{j-1}$ .

This post is about making greedy faster without giving anything up. The trick, due to Minoux (1978)¹, is called Lazy Greedy, and it falls out of taking submodularity seriously.

Recomputing What Can Only Shrink

All that recomputation is wasteful: submodularity guarantees that marginal gains can only decrease over time. If an element had a low marginal gain at step $j-1$ , it will have an even lower gain at step $j$ . Why recompute it?

The gains computed at earlier steps are not exact anymore, but they are still informative: each one is an upper bound on the element’s current gain. Minoux formalized this observation into an algorithm. The idea is to maintain a max-heap (priority queue) of upper bounds on marginal gains:

\boxed{ \begin{aligned} & \textbf{LazyGreedy}(f, \mathcal{V}, k) \\ & \quad S_0 \leftarrow \varnothing \\ & \quad \text{Initialize max-heap } H \text{ with } \rho_e \leftarrow +\infty \text{ for all } e \in \mathcal{V} \\ & \quad \textbf{for } j = 1 \textbf{ to } k\textbf{:} \\ & \quad \quad \textbf{loop:} \\ & \quad \quad \quad e \leftarrow H.\text{pop}() \\ & \quad \quad \quad \rho_e \leftarrow f(e \mid S_{j-1}) \quad \text{// recompute actual gain} \\ & \quad \quad \quad \textbf{if } \rho_e \geq H.\text{peek}()\textbf{:} \\ & \quad \quad \quad \quad S_j \leftarrow S_{j-1} \cup \{e\} \\ & \quad \quad \quad \quad \textbf{break} \\ & \quad \quad \quad \textbf{else:} \\ & \quad \quad \quad \quad H.\text{push}(e, \rho_e) \\ & \quad \textbf{return } S_k \end{aligned} }

At each step, Lazy Greedy pops the element $e$ with the highest upper bound from the heap and recomputes its actual marginal gain. If the recomputed gain is still the largest (i.e., $\rho_e \geq$ the next-highest upper bound in the heap), then by submodularity $e$ must have the largest true marginal gain among all remaining elements. The algorithm selects $e$ and moves on. Otherwise, it pushes $e$ back into the heap with its updated bound and tries the next candidate.

The worst-case runtime is still $\mathcal{O}(n \cdot k)$ ; you might end up recomputing every element at every step. In practice, however, Lazy Greedy often needs only a handful of recomputations per step, because elements whose gains were already low at the previous step are even lower now and stay deep in the heap. The speedup varies depending on the problem instance, but factors of 5x to 100x over standard greedy are common. The approximation guarantee remains $(1 - 1/e)$ , unchanged. Lazy Greedy returns exactly the same solution as standard greedy (up to tie-breaking); it just spends fewer oracle calls to find it.

A Heap of Stale Thunks

If you have worked with lazy evaluation in functional programming, the pattern is familiar: avoid doing work until you know it matters. A thunk is a promise to compute a value later, and forcing it means paying the cost only when the value is actually needed. Each entry $\rho_e$ in Lazy Greedy’s heap can be thought of as a stale thunk: a marginal gain cached at some earlier step, left unforced until the element reaches the top of the heap. Popping the element forces the thunk, which in this setting means one oracle call to recompute $f(e \mid S_{j-1})$ against the current solution.

A memoized thunk caches a value that never changes, so forcing it once settles the matter forever. Lazy Greedy’s cached values do change: every element added to the solution can shrink the true gain of every other element. Submodularity is what rescues the scheme. It guarantees that gains only ever decrease, so a stale value is always an upper bound on the fresh one. A stale bound can flatter an element but never undersell it, and that asymmetry is why a single comparison against the next-best bound is enough to certify a winner.

The two shapes look like this side by side:

stale-thunks.ts

// Ordinary lazy evaluation: force once, cache forever.
function lazy<T>(compute: () => T): () => T {
  let cached: T | undefined;
  return () => (cached ??= compute());
}

// Lazy Greedy: a heap of stale thunks. The cache goes stale on
// purpose, but submodularity keeps it a sound upper bound.
type StaleThunk = {
  element: number;
  bound: number; // marginal gain cached at an earlier step
  force: () => number; // recompute f(e | S) against the current S
};

function selectNext(heap: MaxHeap<StaleThunk>): number {
  const top = heap.pop();
  const fresh = top.force(); // pay the oracle call now
  if (fresh >= heap.peek().bound) return top.element; // still best
  heap.push({ ...top, bound: fresh }); // re-suspend and retry
  return selectNext(heap);
}

Ordinary laziness saves work because values never change. Lazy Greedy saves work because values change in only one direction.

Looking Ahead

Lazy Greedy’s speedup is real but opportunistic. On well-behaved instances the heap prunes almost everything; on adversarial or poorly structured ones it degrades back to standard greedy’s $\mathcal{O}(n \cdot k)$ . For massive datasets ( $n$ in the millions, $k$ in the thousands), we need an algorithm whose theoretical runtime is better, not just one that is faster on benign inputs.

In Part 4, I will introduce the Stochastic Greedy algorithm (Mirzasoleiman et al. 2015)², which replaces the full scan over $\mathcal{V}$ at each step with a random subsample of size $\mathcal{O}((n/k) \ln(1/\varepsilon))$ . The total cost drops from $\mathcal{O}(n \cdot k)$ to $\mathcal{O}(n \cdot \ln(1/\varepsilon))$ ; the factor of $k$ becomes a logarithmic term. The approximation guarantee degrades only slightly, to $(1 - 1/e - \varepsilon)$ in expectation, where $\varepsilon > 0$ is a tunable parameter.

Key Takeaways

Lazy Greedy exploits the diminishing returns property to skip redundant recomputations: a marginal gain cached at an earlier step is always an upper bound on the current one.
A max-heap of stale bounds plus one comparison against the next-best bound is enough to certify each pick, so the algorithm returns the same solution as standard greedy with the same $(1 - 1/e)$ guarantee.
Speedups of 5x to 100x are common in practice, but the worst-case cost remains $\mathcal{O}(n \cdot k)$ , which motivates the Stochastic Greedy algorithm in Part 4.

Recomputing What Can Only Shrink

A Heap of Stale Thunks

Looking Ahead

Key Takeaways

Further Reading