4
$\begingroup$

in papers regarding stochastic optimization methods such as for example SGD people often talk about the variance of the gradient $g$ and mostly it is expressed expressed as follows:

$$ \operatorname {Var}(g_r) = E(\|g-E(g)\|_2^2)=E(\|g\|^2_2)-\|E(g)\|_2^2 $$

This reminds me of the standard variance definition for a random variable $X$, that is: $$\operatorname {Var} (X)=\operatorname {E} \left[(X-\operatorname {E}(X))^{2}\right]=\operatorname {E}(X^2)-\operatorname {E}(X)^2$$.

So here is what confuses me:

  • In the above expression we have $\operatorname {Var} (g)$, not $\operatorname {Var} (\|g\|)$. So why does the l2-norm show up here?
  • $g_r$ is a vector-valued random variable, with values in ${\displaystyle \mathbb {R} ^{n}}$.For vector valued random variables, the Variance should be $ \operatorname {E} ((X-\mu )(X-\mu )^{\operatorname {T} })$, i.e. the variance-covariance matrix. Why do we still apply the other formula here?

I'm not an expert in stats and would thus much appreciate some clarification.

Thank you in advance!

$\endgroup$
6
$\begingroup$

I gave this issue some more thoughts and came to the following conclusion: Most of the papers that deal with variance reduction for SGD (methods such as SVRG, SAGA, and SAG) actually mean the 1-norm of the variance of the gradients (trace of cov-matrix) when they write $\operatorname{Var}(g)$.

Assuming that the stochastic gradients $g \in \mathbb{R}^p$ are unbiased estimator of the true gradient we have:

\begin{equation} \begin{aligned} \| \text{diag}(\operatorname{Cov}(g))\|_1= \|\operatorname{Var}(g)\|_1=&|\operatorname{E}(g^1-\nabla f^1)^2|+...+ |\operatorname{E}(g^p-\nabla f^p)^2| \\ =& \operatorname{E}((g^1-\nabla f^1)^2+...+(g^p-\nabla f^p)^2) \\=&\operatorname{E}(\|g-\nabla f\|_2^2)\\=&\operatorname{E}(\|g\|^2)-\|\nabla f\|^2\\=&\operatorname{E}(\|g\|^2)-\|\operatorname{E}(g) \|^2\\ \overset{def}{=}& \operatorname{Var}(g) \end{aligned} \end{equation}

$\endgroup$
  • $\begingroup$ you can accept your own answer $\endgroup$ – javadba Feb 6 '18 at 16:40

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.