Stochastic-Greedy Linear-Time Monotone Submodular Maximization

Stochastic-Greedy Linear-Time Monotone Submodular Maximization is a randomized combinatorial optimization algorithm introduced by Mirzasoleiman, Badanidiyuru, Karbasi, Vondrak, and Krause (2015) for maximizing a non-negative monotone submodular set function f: 2^V -> R_+ over a ground set V of size n subject to a cardinality constraint |A| <= k. Whereas the classical Nemhauser-Wolsey-Fisher greedy algorithm evaluates all n - |A_{i-1}| remaining elements at each of the k steps (requiring O(n k) function evaluations) and Minoux's Lazy-Greedy maintains priority-queue upper bounds rho(e) with worst-case O(n k) cost, `Stochastic-Greedy` (Algorithm 1) starts with A_0 = empty and in each iteration i = 1, ..., k draws a uniformly random subset R subseteq V \ A_{i-1} of size s = (n/k) log(1/epsilon) and adds the element a_i = argmax_{a in R} Delta(a | A_{i-1}) maximizing marginal gain Delta(a | A) = f(A union {a}) - f(A) within R (optionally accelerated further via lazy upper-bound evaluations on R). Lemma 2 proves that R overlaps the residual optimal set A^* \ A_{i-1} with probability Pr[R cap (A^* \ A_{i-1}) != empty] >= (1 - epsilon)|A^* \ A_{i-1}| / k, yielding expected one-step marginal gain E[Delta(a_i | A_{i-1}) | A_{i-1}] >= ((1 - epsilon)/k) * sum_{a in A^* \ A_{i-1}} Delta(a | A_{i-1}) >= ((1 - epsilon)/k)*(f(A^*) - f(A_{i-1})), and Theorem 1 proves that `Stochastic-Greedy` achieves E[f(A_k)] >= (1 - 1/e - epsilon) f(A^*) in at most k * (n/k) log(1/epsilon) = n log(1/epsilon) function evaluations—linear in n and completely independent of the cardinality constraint k.