There is a summation-index misprint. On the native PDF, paper page 3, equation (4) has

X^{k}

inside a sum indexed by

j

. The intended telescoping estimate has

X^{j}

inside that sum; this is the estimate proved below and used in part (d). The index mismatch is present in the original PDF, rather than being introduced by the transcription.

Take the expectation of the supplied conditional expectation bound (3), using the tower property:

E f (X^{j + 1}) \leq E f (X^{j}) - \frac{1}{2 L} E ∥\nabla f (X^{j}) ∥^{2} + \frac{M}{2 L} .

(1)

Rearranging and forming a telescoping sum gives

\frac{1}{2 L} \sum_{j = 0}^{k - 1} E ∥\nabla f (X^{j}) ∥^{2} \leq f (x^{0}) - E f (X^{k}) + \frac{k M}{2 L} .

(2)

Because

x^{*}

is a global minimizer,

f (X^{k}) \geq f (x^{*})

for every realisation. Hence the corrected equation (4) is

j = 0 \sum k - 1 \frac{1}{2 L} E ∥\nabla f (X^{j}) ∥^{2} \leq f (x^{0}) - f (x^{*}) + \frac{k M}{2 L} .

(3)

All expectations at a finite iteration are finite here: a deterministic starting point and finitely many choices of the sampled index produce only finitely many possible iterates. The bound controls accumulated squared gradients, with an additive contribution from the stochastic gradient noise floor.