1
$\begingroup$

This is a question about the difference in gradient noise or variance of gradient for stochastic gradient descent vs mini-batch gradient descent (with batch size $B \geq 1$).

How can I prove that the variance of gradient for the batch gradient descent is reduced by a factor of $B$ compared to stochastic gradient descent?

Any links to papers would be helpful too.

$\endgroup$

2 Answers 2

1
$\begingroup$

By induction, you can show that for $i=1$, it is trivial. For any $t \leq m - 1$, assume that $E((\frac{\sum_{i=1}^tX_i}{t}-E(X))^2)=\frac{E(X^2) - E(X)^2}{t}$, when $t = m$, one has

$$ E((\frac{\sum_{i=1}^mX_i}{m}-E(X))^2) = E((\frac{\sum_{i=1}^{m-1}X_i-(m-1)E(X) + (X_m - E(X))}{m})^2) = \frac{1}{m^2}(E((\sum_{i=1}^{m-1}X_i-(m-1)E(X))^2) + E((X_m-E(X))^2) + E(2(\sum_{i=1}^{m-1}X_i-(m-1)E(X))(X_m - E(X)))) = \frac{1}{m^2}((m-1)E(X^2) - (m-1)E(X)^2 + E(X^2)-E(X)^2) = \frac{E(X^2) - E(X)^2}{m} $$

The third equality used fact that $X_1, \ldots, X_m$ are drawn independently. You may replace $m$ with $B$ in your formula.

$\endgroup$
0
$\begingroup$
Given X random, then it has some variance (denote it by v), then we have   

$$ \mathbb{V}[\frac{\sum_{i=1}^B X_i}{B}] = \frac{\sum_{i=1}^B \mathbb{V}[X_i]}{B^2} = \frac{Bv}{B^2} = v/B $$ Of course the insertion of variance inside the sum because $X_i$ are i.i.d., otherwise covariance comes to play.

$\endgroup$
1
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Commented May 23, 2023 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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