k$, and $B_i^{kl}$ equals the zero matrix, otherwise.

Lemma \[lemma:3\] provides the tool to reduce the iteration $t$ by one. Therefore, we can easily use it to recursively calculate the norm of any linear combinations of the sample-wise gradients, for all iterations $t$. Combining the fact that $c_b$ is a decreasing function of $b$, we are able to show Theorem \[thm:1\].

\[thm:1\] For any $t \in \naturals$ and any matrices $A_i \in \mathbb{R}^{p\times p}, i\in[n]$, $\condexp{}{\norm{\sum_{i=1}^{n} A_i \grad L_i\pth{w_{t}^b}}^2}{\calF_0}$ is a decreasing function of $b$ for $b \in [n]$.

Theorem \[thm:1\] states that the norm of any linear combinations of the sample-wise gradients is a decreasing function of $b$. Combining Lemma \[lemma:1\] which connects the variance of $g_t^b$ with the linear combination of $\grad L_i\pth{w_{t}^b}$’s, and the fact that $\grad L\pth{w_{t}^b} = \frac{1}{n}\sum_{i=1}^n\grad L_i\pth{w_{t}^b}$, we have Theorem \[thm:2\].

\[thm:2\] Fixing initial weights $w_0$, both $\var\left(Bg_t^b \, \middle| \calF_0 \right)$ and $\var\left(B\grad L\pth{w_t^b} \, \middle| \calF_0 \right)$ are decreasing functions of mini-batch size $b$ for all $b \in [n]$, $t \in \naturals$, and all square matrices $B \in \mathbb{R}^{p \times p}$.

As a special case, Corollary \[col:1\] guarantees that the variance of the stochastic gradient estimator is a decreasing function of 