I'm going through the JMLR paper on distributed mini-batch Stochastic Gradient Descent and I have a question about a part of the proof.

They use the notation:

$$F(w) = \mathop{\mathbb{E}}_{z}[f(w, z)]$$

where $f(w, z)$ is the loss function, $z$ the inputs and $w$ the predictions.

In the proof of Theorem 3 (pages 8 and 9) they claim --$\langle\rangle$ indicate vector inner product--:

Notice that $z_s$ and $z_{s'}$ are independent whenever $s \neq s'$, and in such cases:

$$\mathop{\mathbb{E}}\langle\nabla_w f(w, z_s) - \nabla F(w), \nabla_w f(w, z_{s'}) - \nabla F(w) \rangle \\= \langle\mathop{\mathbb{E}}[\nabla_w f(w, z_s) - \nabla F(w)], \mathop{\mathbb{E}}[\nabla_w f(w, z_{s'}) - \nabla F(w)] \rangle = 0$$

i.e. the expectation of the inner product of the two values is equal to the inner product of their expectations, which is equal to zero.

What I'm not sure about is why the inner product of the expectations is zero given the assumption of independent $z_s$ and $z_{s'}$.

Am I right to assume that independence of vectors implies orthogonality and therefore 0 inner product? Or is it that the expected values of the two quantities is 0, and therefore their inner product is 0?

• it would be nice if you can make ur title more descriptive. There are millions of papers and millions of proof. – Charlie Parker Apr 27 '16 at 21:35

Independence means that $E[XY]=E[X]E[Y]$wikipedia
$F(w)=E_z[f(w,z)]$
$\nabla_w F(w)=\nabla_w E_z[f(w,z)]=E_z[\nabla_w f(w,z)]$
• Let's take the first element of the inner product: $E[\nabla_w f(w, z_s) - \nabla E_z [f(w,z)] = E[\nabla_w f(w, z_s) - E_z[ \nabla f(w,z)]$ Don't the subscripts in the first nabla (w) and the second expectation (z) affect the result? Note that the second expectation is over z only. – Bar Apr 9 '15 at 15:43