the full gradient, e.g. Assumption 4.3 in [@bottou2018optimization]. One exception is [@gower2019sgd] which gives more precise bounds of the variance under different sampling methods. These bounds are still dependent on the model parameters at the corresponding iteration. To the best of the authors’ knowledge, there is no existing result connecting the variance of stochastic gradient estimators with the initial weights and the mini-batch size. This paper partially solves this problem.

Analysis {#sec:3}
========

Mini-batch SGD is a lighter-weight version of gradient descent. Suppose that we are given a loss function $L(w)$ where $w$ is the collection (vector, matrix, or tensor) of all model parameters. At each iteration $t$, instead of computing the full gradient $\grad_w L(w_t)$, SGD randomly samples a mini-batch set $\calB_t$ that consists of $b=|\calB_t|$ training instances and sets $$w_{t+1} \gets w_t - \alpha_t \grad_w L_{\calB_t}(w_t),$$ where the positive scalar $\alpha_t$ is the learning rate (or step size) and $\grad_w L_{\calB_t}(w_t)$ denotes the stochastic gradient estimator based on mini-batch $\calB_t$.

An important property of the stochastic gradient estimator $\grad_w L_{\calB_t}(w_t)$ is that it is an unbiased estimator, i.e. $\mathbb{E} \grad_w L_{\calB_t}(w_t) = \grad_w L(w_t)$, where the expectation is taken over all possible choices of mini-batch $\calB_t$. However, it 