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 $s = \dfrac{n}{k}log\dfrac{1}{\epsilon}$. Then STOCHASTIC-GREEDY achieves a $(1 - \dfrac{1}{e} - \epsilon)$ guarantee in expectation to the optimum solution with only $O(n *log \dfrac{1}{\epsilon})$ function evaluations.

The remarkable thing about this bound on the number of function evaluations is that it does not depend on $k$. Remember, the greedy algorithm has a $(1 - \dfrac{1}{e})$ guarantee, but $O(n * k$) function evaluations.

Let's say we set $\epsilon = 0.01$, so that we get an approximation of $\approx 0.62$. This would mean we would need $O(5n)$ function evaluations - roughly the same as running the greedy algorithm for $k =5$ - 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 $A$, the expected gain of STOCHASTIC-GREEDY in one step is at least $\dfrac{1 - \epsilon}{k}\sum_{a \in A^* \setminus A} \Delta(a \vert A)$

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 $R \cap (A^* \setminus A) \ne \emptyset$. The set $R$ consists of $s = \dfrac{n}{k}log\dfrac{1}{\epsilon}$ random samples from $V \setminus A$ (w.l.o.g. with repetition), and hence

$$\begin{align} P(R \cap (A^* \setminus A) = \emptyset) &= \left(1 - \frac{|A^* \setminus A|}{|V \setminus A|}\right)^s & \text{basic probability}\\ &\leq e^{-s \frac{|A^* \setminus A|}{|V \setminus A|}} & \text{$1 - x \leq e^{-x}$}\\ &\leq e^{-\frac{s}{n}|A^* \setminus A|} & \text{$|V \setminus A| \leq n$, since $|V| = n$} \end{align}$$

Now, $P(R \cap (A^* \setminus A) \ne \emptyset) = 1 - P(R \cap (A^* \setminus A) = \emptyset) \geq 1 - e^{-\frac{s}{n}|A^* \setminus A|}$. Now recall that by definition, a concave function $f$ is such that:

$$f((1-\alpha) a+ \alpha b) \geq (1-\alpha ) f(a)+\alpha f(b) \quad \forall a,b, \quad 0 \le \alpha \le 1$$

Since $e^x$ is convex, $1 - e^x$ is concave. Let $f = 1 - e^{-\frac{s}{n}x}$. Note that $\vert A^* \setminus A \vert \leq k$, since $\vert A^* \vert = k$.

Setting $\alpha = \dfrac{\vert A^* \setminus A \vert}{k}$, $a=0$ and $b=k$ gives us:

$$\underbrace{1 - e^{-\frac{s}{n}|A^* \setminus A|}}_{f(\alpha * b)} \geq \underbrace{0}_{(1 - \alpha) f(a)} + \underbrace{(1 - e^{\frac{sk}{n}})}_{f(b)}\underbrace{\dfrac{|A^* \setminus A|}{k}}_{\alpha}$$

And thus:

$$P(R \cap (A^* \setminus A) \ne \emptyset) \geq 1 - e^{-\frac{s}{n}|A^* \setminus A|} \geq \left(1 - e^{-\frac{sk}{n}}\right)\frac{|A^* \setminus A|}{k}$$

Since we choose $s = \dfrac{n}{k}log\dfrac{1}{\epsilon}$:

$$P(R \cap (A^* \setminus A) \ne \emptyset) \geq (1 - \epsilon)\frac{|A^* \setminus A|}{k}\tag{3}$$

Since STOCHASTIC-GREEDY picks the element $a$ that maximizes $\Delta(a \vert A)$, it is obvious that $\Delta(a \vert A) \geq \Delta(b \vert A)$ for any $b \in R \cap (A^* \setminus A)$ (if nonempty). Since $R$ is equally likely to contain any element of $A^* \setminus A$, a uniformly random element of $R \cap (A^* \setminus A)$ is a uniformly random element of $A^* \setminus A$. Thus:

$$E[\Delta(a|A)] \geq P(R\cap (A^* \setminus A) \ne 0) * \underbrace{\frac{1}{|A^* \setminus A|}\sum_{b \in A^* \setminus A}\Delta(b|A)}_{E[\Delta(b|B) ]}$$

The inequality is true because we're taking expectation over two events: $R\cap (A^* \setminus A) \ne 0$ and $R\cap (A^* \setminus A) = 0$. Since the gain of the second event times its probability is non-negative, we have the inequality.

Plugging (3) in, we have:

$$E[\Delta(a|A)] \geq \frac{1 - \epsilon}{k}\sum_{b \in A^* \setminus A}\Delta(b|A)$$

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

Let $A_i = \{a_1, ..., a_i\}$ be the solution returned by STOCHASTIC-GREEDY after $i$ steps. From Lemma 2,

$$E[\Delta(a_{i+1}|A_i)] \geq \frac{1 - \epsilon}{k}\sum_{a \in A^* \setminus A_i}\Delta(a|A)$$

By submodularity,

$$\sum_{a \in A^* \setminus A_i}\Delta(a|A) \geq \underbrace{\Delta(A^* | A_i)}_{f(A^* \cup A_i) - f(A_i)} \underbrace{\geq}_{\text{monotonicity}} f(A^*) - f(A_i)$$

Therefore,

$$\underbrace{E[\Delta(a_{i+1} | A_i)]}_{E[f(A_{i+1}) - f(A_i)]} \geq \frac{1 - \epsilon}{k}\left(f(A^*) - f(A_i)\right)$$

Now remembering the law of total expectation ($E[E[x \vert y]] = E[x]$) and taking expectation over $A_i$:

$$E[f(A_{i+1}) - f(A_i)] \geq \frac{1 - \epsilon}{k}E\left[f(A^*) - f(A_i)\right]$$

Rearranging:

$$E[F(A_{i+1})] \geq \frac{1 - \epsilon}{k}\underbrace{E[f(A^*)]}_{= f(A^*)} - (\frac{1 - \epsilon}{k} - 1)E[f(A_i)]$$

Applying this to $E[F(A_k)]$ and expanding the recursion gives:

$$E[F(A_{k})] \geq \frac{1 - \epsilon}{k}f(A^*)\left(\sum_{i=0}^{k-1}(1 - \frac{1 - \epsilon}{k})^i\right)$$

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

$$\begin{align} E[F(A_{k})] &\geq \left(1 - \left(1 - \frac{1 - \epsilon}{k}\right)^k\right)f(a^*)\\ &\geq \left(1 - e^{-(1 - \epsilon)}\right)f(A^*) & \text{using $e^{-x} \geq 1-x$} \\ &\geq (1 - \frac{1}{e} - \epsilon)f(A^*) \end{align}$$

To see why the second inequality is true, we show that $e^{-(1 - \epsilon)} \leq \frac{1}{e} + \epsilon$ for $\epsilon \in [0,1]$.

First, take $\epsilon = 0$. 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 $e^{-(1 - \epsilon)}$, which is smaller or equal to $1$ for any $\epsilon \in[0,1]$.

This finishes the proof.