Lazier than Lazy Greedy

We will be going step-by-step through this paper. Please refer back to this post for the definitions we need for submodularity and the greedy algorithm. The algorithm is as follows:

The main result is in Theorem 1, restated below:

Theorem 1. Let f be a non-negative monotone submodular function. Let us also set . Then STOCHASTIC-GREEDY achieves a guarantee in expectation to the optimum solution with only function evaluations.

The remarkable thing about this bound on the number of function evaluations is that it does not depend on . Remember, the greedy algorithm has a guarantee, but ) function evaluations.

Let's say we set , so that we get an approximation of . This would mean we would need function evaluations - roughly the same as running the greedy algorithm for - but now we can get a set of any size.

We now go step by step through the proof, presented in the appendix.

Lemma 2. Given a current solution , the expected gain of STOCHASTIC-GREEDY in one step is at least

Note how similar this Lemma is to the bound we proved in the first array of equations for the greedy algorithm

Proof. Let us estimate the probability that . The set consists of random samples from (w.l.o.g. with repetition), and hence

Now, . Now recall that by definition, a concave function is such that:

Since is convex, is concave. Let . Note that , since .

Setting , and gives us:

And thus:

Since we choose :

Since STOCHASTIC-GREEDY picks the element that maximizes , it is obvious that for any (if nonempty). Since is equally likely to contain any element of , a uniformly random element of is a uniformly random element of . Thus:

The inequality is true because we're taking expectation over two events: and . Since the gain of the second event times its probability is non-negative, we have the inequality.

Plugging (3) in, we have:

Notice I changed notation a bit (using instead of in the RHS to avoid confusion). Thus, we have proved Lemma 2.

Let be the solution returned by STOCHASTIC-GREEDY after steps. From Lemma 2,

By submodularity,

Therefore,

Now remembering the law of total expectation () and taking expectation over :

Rearranging:

Applying this to and expanding the recursion gives:

Using the formula for the sum of a geometric series, we get

To see why the second inequality is true, we show that for .

First, take . The inequality becomes an equality.

Now, we show that the derivative of the RHS is always greater or equal to the derivative of the LHS. The derivative of the RHS is 1. The derivative of the LHS is , which is smaller or equal to for any .

This finishes the proof.

Written on July 21, 2015