0
$\begingroup$

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?

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

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)]$

$\endgroup$
  • $\begingroup$ I still don't understand, how does this relate to the inner product of the two values being zero? $\endgroup$ – Bar Apr 9 '15 at 15:15
  • $\begingroup$ because the inner product is of the form <x-x,y-y> $\endgroup$ – seanv507 Apr 9 '15 at 15:27
  • $\begingroup$ 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. $\endgroup$ – Bar Apr 9 '15 at 15:43
  • $\begingroup$ both nablas are differentiating wrt (F is only function of w), and w is kept constant so nothing else to take expectation over? $\endgroup$ – seanv507 Apr 9 '15 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.